Question 54 : How to reverse a linked list in pairs?

 You need to write a java program to reverse linked list in pairs.

There can be two solution for reversing linked list in pairs

• Iterative
• Recursive

Iterative:

The logic for this would be:

public static Node reverseLinkedListInPairItr(Node head) {
 
    Node current=head;
    Node temp=null;
    Node newHead =null;
    while (current != null && current.next != null) {
 
        if (temp != null) {
            // This is important step
            temp.next.next = current.next;
        }
        temp=current.next;
        current.next=temp.next;
        temp.next=current;
 
        if (newHead == null)
            newHead = temp;
        current=current.next;
 
    }
    return newHead;
}

Explanation:

Lets understand with the help of simple example:
Lets say linkedlist is 5-> 6 -> 7 -> 1
If you look closely, below steps are just reversing link to  6->5->7->1 in first iteration (Swapping node 6 and 5) and then advance to next pair (Node 7 and 1)

// Node 6 is temp node
temp=current.next;
// putting link between 5->7
current.next=temp.next;
// putting link between 6->5
temp.next=current;
// 6 becomes he

You must be wondering why we have put below code:

if (temp != null) {
      // This is important step
      temp.next.next = current.next;
}

before swapping two nodes , we need to link nodes properly. When we are swapping 7 and 1 , link between 5->7 will be broken and we need to connect node 5 to node 1.

As per above code , temp will be null in first iteration(swapping node 6 and 5) but when current node is 7, temp will be 6, here we are linking nodes as below
6->5->1->7

Java program for this will be :

public class ReverseLinkedListInPair{
 
    private Node head;
 
    private static class Node {
        private int value;
        private Node next;
 
        Node(int value) {
            this.value = value;
 
        }
    }
 
    public void addToTheLast(Node node) {
 
        if (head == null) {
            head = node;
        } else {
            Node temp = head;
            while (temp.next != null)
              temp = temp.next;
 
            temp.next = node;
        }
    }
 
    public void printList(Node head) {
        Node temp = head;
        while (temp != null) {
            System.out.format("%d ", temp.value);
            temp = temp.next;
        }
        System.out.println();
    }
 
    // Reverse linked list in pair
    public static Node reverseLinkedListInPairs(Node head) {
 
        Node current=head;
        Node temp=null;
        Node newHead =null;
        while (current != null && current.next != null) {
 
            if (temp != null) {
                // This is important step
                temp.next.next = current.next;
            }
            temp=current.next;
            current.next=temp.next;
            temp.next=current;
 
            if (newHead == null)
                newHead = temp;
            current=current.next;
 
        }
        return newHead;
    }
 
    public static void main(String[] args) {
        ReverseLinkedListInPair list = new ReverseLinkedListInPair();
        // Creating a linked list
        Node head=new Node(5);
        list.addToTheLast(head);
        list.addToTheLast(new Node(6));
        list.addToTheLast(new Node(7));
        list.addToTheLast(new Node(1));
        list.addToTheLast(new Node(2));
        list.addToTheLast(new Node(8));
 
        list.printList(head);
        //Reversing LinkedList in pairs
        Node result=reverseLinkedListInPairs(head);
        System.out.println("After reversing in pair");
        list.printList(result);
    }
}

Run above program, you will get following output:

5 6 7 1 2 8
After reversing
6 5 1 7 8 2

Recursive:

Base case: Base case for this would be either node is null or node.next is null

For recursive solution, replace reverseLinkedListInPairs of above program to below function

public static Node reverseLinkedListInPairs(Node head) {
      if (head == null || head.next == null) {
          return head;
      }
  // Lets take example of 5->6->7
  // Here head node is 5
  // Storing 6 in temp node, it will become our new head
     Node temp=head.next;
  // Putting link between 5->7
     head.next=temp.next;
  // putting link between 6->5
     temp.next=head;
  // recursively calling the function for node 7
     head.next=reverseLinkedListInPairRec(head.next);
  // returning new head
     return temp;
  }.

Don't miss the next article! 
Be the first to be notified when a new article or Kubernetes experiment is published.                            

 

 Share This

• Facebook

• Twitter

• Linkedin

• Pinterest