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 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

You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS