## Wednesday, May 4, 2022

### 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 temp=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;

current=current.next;

}
}``````

#### 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;
current.next=temp.next;
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 static class Node {
private int value;
private Node next;

Node(int value) {
this.value = value;

}
}

} else {
while (temp.next != null)
temp = temp.next;

temp.next = node;
}
}

while (temp != null) {
System.out.format("%d ", temp.value);
temp = temp.next;
}
System.out.println();
}

// Reverse linked list in pair

Node temp=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;

current=current.next;

}
}

public static void main(String[] args) {

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) {
}
// Lets take example of 5->6->7
// Here head node is 5
// Storing 6 in temp node, it will become our new head