Given a singly linked list, write a function to swap elements pairwise. For example, if the linked list is 1->2->3->4->5 then the function should change it to 2->1->4->3->5, and if the linked list is 1->2->3->4->5->6 then the function should change it to 2->1->4->3->6->5.

 METHOD 1 (Iterative)
Start from the head node and traverse the list. While traversing swap data of each node with its next node’s data
Java Programming:
// Java program to pairwise swap elements of a linked list
class LinkedList
{
    Node head;  // head of list
  
    /* Linked list Node*/
    class Node
    {
        int data;
        Node next;
        Node(int d) {data = d; next = null; }
    }
 
    void pairWiseSwap()
    {
        Node temp = head;
 
        /* Traverse only till there are atleast 2 nodes left */
        while (temp != null && temp.next != null) {
 
            /* Swap the data */
            int k = temp.data;
            temp.data = temp.next.data;
            temp.next.data = k;
            temp = temp.next.next;
         }
    }
 
                     
    /* Utility functions */
 
    /* Inserts a new Node at front of the list. */
    public void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                  Put in the data*/
        Node new_node = new Node(new_data);
  
        /* 3. Make next of new Node as head */
        new_node.next = head;
  
        /* 4. Move the head to point to new Node */
        head = new_node;
    }
 
    /* Function to print linked list */
    void printList()
    {
        Node temp = head;
        while (temp != null)
        {
           System.out.print(temp.data+" ");
           temp = temp.next;
        }  
        System.out.println();
    }
 
    /* Driver program to test above functions */
    public static void main(String args[])
    {
        LinkedList llist = new LinkedList();
 
        /* Created Linked List 1->2->3->4->5 */
        llist.push(5);
        llist.push(4);
        llist.push(3);
        llist.push(2);
        llist.push(1);
         
        System.out.println("Linked List before calling pairWiseSwap() ");
        llist.printList();
         
        llist.pairWiseSwap();
         
        System.out.println("Linked List after calling pairWiseSwap() ");
        llist.printList();
    }
} 
/* This code is contributed by Rajat Mishra */

Output:

Linked List before calling pairWiseSwap() 
1 2 3 4 5 
Linked List after calling pairWiseSwap() 
2 1 4 3 5

Time complexity: O(n)

METHOD 2 (Recursive)
If there are 2 or more than 2 nodes in Linked List then swap the first two nodes and recursively call for rest of the list.

 Java Programming:
/* Recursive function to pairwise swap elements of a linked list */
void pairWiseSwap(struct node *head)
{
  /* There must be at-least two nodes in the list */
  if (head != NULL && head->next != NULL)
  {
      /* Swap the node's data with data of next node */
      swap(&head->data, &head->next->data);
    
      /* Call pairWiseSwap() for rest of the list */
      pairWiseSwap(head->next->next);
  }  
}
Time complexity: O(n)

Categorized in:

Linked ListSingly Linked List

Tagged in:

, , , , , , , , ,