Linked List: Program to pairwise swap nodes of a linked list


Write a program to swap the nodes pair wise in a linked list

Basic idea for the problem is that, we traverse the list using three pointers and
change the links of pairwise nodes. Then move to the next pairwise nodes and change their links and so on.

For example,
given linked list is -
1 -> 2 -> 3 -> 4
After pairwise swapping the linked list will look like
2 -> 1 -> 4 -> 3

 
Algorithm
  1. If head or head.next is NULL then return from function
  2. Create three pointers
    • pointer 'before' pointing to head
    • pointer 'current' pointing to head.next
    • pointer 'after'
  3. while true
    • set after as current.next
    • set current.next as before
    • check if after or after.next is NULL
      • set before.next = after
      • return
    • set before.next = after.next
    • set before = after
    • set current = before.next
 
Complexity

Time Complexity : O(n) , where n is the number of nodes in the linked list
Space Complexity : O(1)

 
Java Code
 import java.util.*;

 class SwapNodesPairWise{
        
        class Node {
            int data;
            Node next;
         
            Node(int d) {
                this.data = d;
                this.next = null;
            }
        }
    
        Node head;
     
        // creating a linked list using array
        public void buildLinkedlist(int A[], int noOfNodes) {
            int i;
            Node temp, last;
            temp = new Node(A[0]);
            temp.next = null;
            head = temp;
            last = temp;
            for (i = 1; i < noOfNodes; i++) {
                temp = new Node(A[i]);
                temp.next = null;
                last.next = temp;
                last = temp;
            }
        }
     
        // printing of linkedList
        public void printLinkedlist() {
            List allNodesList = new ArrayList<>();
            Node temp = head;
            while (temp != null) {
                allNodesList.add(Integer.toString(temp.data));
                temp = temp.next;
            }
            System.out.println(String.join(" -> ", allNodesList));
        }
     
        public void pairWiseSwap() {
            if (head == null || head.next == null) {
                return;
            }
    
            Node before = head;
            Node current = head.next;
            Node after;
             
            head = current;
            
            while (true) {
                after = current.next;
                current.next = before;
    
                if (after == null || after.next == null) {
                    before.next = after;
                    break;
                }
    
                before.next = after.next;
                before = after;
                current = before.next;
            }
        }
     
        public static void main(String[] args) {
            int[] linkedlistElements = new int[] { 1, 2, 3, 4, 5, 6 };
            int numberOfNodes = linkedlistElements.length;
            // initialising object of linkedlist class
            SwapNodesPairWise ll1 = new SwapNodesPairWise();
            ll1.buildLinkedlist(linkedlistElements, numberOfNodes);
            System.out.println("Given linked list ");
            ll1.printLinkedlist();
            System.out.println("After pairwise swapping nodes ");
            ll1.pairWiseSwap();
            ll1.printLinkedlist();
     
        }
  }
Output

Given linked list
1 -> 2 -> 3 -> 4 -> 5 -> 6
After pairwise swapping nodes
2 -> 1 -> 4 -> 3 -> 6 -> 5



Thanks for feedback.



Read More....
Clone a Linked List
Find the middle of linked list with odd no of nodes
Check if linked list nodes form a palindrome
Delete a node at specific position from linked list
Delete a node from linked list
Detect if cycle is present in a linked list