Reverse a linked list in pairs (alternate pairs of nodes) - Recursive and Iterative

byNikhil Ranjan •
1
Problem Statement :- Reverse a linked list in such a way that, pair of elements are reversed and linked list internal structure is maintained. Solve using recursive and non-recursive approach.
Sample Input and Output:- 
Inputs:  12 --> 18 -->  172 --> 62 --> 632 --> 192 --> 34
Output:  18 --> 12 -->  62  --> 172 --> 192 --> 632 --> 34
Inputs:  12 --> 18 -->  172 --> 62 --> 632 --> 192 
Output:  18 --> 12 -->  62  --> 172 --> 192 --> 632

Recursive implementation - reverse a linked list in pairs 

Algorithm:-
1) Reverse pair of nodes of  input list and store references of next pair of nodes using next2nextNode. keep track of previous node using previous reference.
2) Recursively call for rest of the list and link the two sub-lists(head.next = reverseLinkedListInPairsRecursive(next2nextNode) )
3) Since, previous is storing first node of each pair, so return previous as new head of the list.
4) Check for special cases for empty list and one node list.
/* Recursive- Reverses the linked list in pairs and returns new head node. */
private Node reverseLinkedListInPairsRecursive(Node head) {
 Node current = head;
 Node nextNode = null;
 Node next2nextNode = null;
 Node previous = null;
 /* Check for empty and one node list */
 if (current == null || current.next == null)
  return current;

 /* Reverse pair of nodes - check current and current.next is not null */
 if (current != null && current.next != null) {
  nextNode = current.next;
  next2nextNode = nextNode.next;
  current.next = previous;
  nextNode.next = current;
  previous = nextNode;
 }
 /*
  * Recursive call for next pairs and make rest of the list as next of
  * first node
  */
 if (nextNode != null) {
  head.next = reverseLinkedListInPairsRecursive(next2nextNode);
 }

 /* Return previous as new head of the input list */
 return previous;
}

Iterative approach / Non-recursive implementation - reverse a linked list in pairs

Algorithm:-
1. Check for he null list or one node list, if true return that node.
2. Loop the list, until current node and next node is not null, revert pair of node references(if Node1 - > Node2 it becomes Node2 -> Node1)
3. Update previous reference and head(only first iteration).
4. Finally, check for isolated node, and return modified head.
/* Iterative- Reverses the linked list in pairs and returns new head node. */
private Node reverseLinkedListInPairsIterative(Node head) {
 Node current = head;
 Node nextNode = null;
 Node next2nextNode = null;
 Node previous = null;

 /* Check for empty and one node list */
 if (current == null || current.next == null)
  return current;

 /* Loop rest of the list and reverse pairs of nodes */
 while (current != null && current.next != null) {
  /* Swap references of two nodes */
  nextNode = current.next;
  next2nextNode = nextNode.next;
  nextNode.next = current;
  current.next = next2nextNode;

  /*
   * Update previous.next and head :- head is updated for first time
   * and after that update previous.next to connect next pairs
   */
  if (previous == null) {
   head = nextNode;
  } else {
   previous.next = nextNode;
  }

  previous = current;
  current = next2nextNode;
 }
 /* Check for isolated node in pairs - when one node is left */
 if (current != null) {
  previous.next = current;
 }
 /* Return modified head of the list */
 return head;
}

Complete sample program - recursive and iterative implementation 

package com.devinline.linkedlist;

public class ReverseLinkedListElementsInPairs {
 /* Recursive- Reverses the linked list in pairs and returns new head node. */
 private Node reverseLinkedListInPairsRecursive(Node head) {
  Node current = head;
  Node nextNode = null;
  Node next2nextNode = null;
  Node previous = null;
  /* Check for empty and one node list */
  if (current == null || current.next == null)
   return current;

  /* Reverse pair of nodes - check current and current.next is not null */
  if (current != null && current.next != null) {
   nextNode = current.next;
   next2nextNode = nextNode.next;
   current.next = previous;
   nextNode.next = current;
   previous = nextNode;
  }
  /*
   * Recursive call for next pairs and make rest of the list as next of
   * first node
   */
  if (nextNode != null) {
   head.next = reverseLinkedListInPairsRecursive(next2nextNode);
  }

  /* Return previous as new head of the input list */
  return previous;
 }

 /* Iterative- Reverses the linked list in pairs and returns new head node. */
 private Node reverseLinkedListInPairsIterative(Node head) {
  Node current = head;
  Node nextNode = null;
  Node next2nextNode = null;
  Node previous = null;

  /* Check for empty and one node list */
  if (current == null || current.next == null)
   return current;

  /* Loop rest of the list and reverse pairs of nodes */
  while (current != null && current.next != null) {
   /* Swap references of two nodes */
   nextNode = current.next;
   next2nextNode = nextNode.next;
   nextNode.next = current;
   current.next = next2nextNode;

   /*
    * Update previous.next and head :- head is updated for first time
    * and after that update previous.next to connect next pairs
    */
   if (previous == null) {
    head = nextNode;
   } else {
    previous.next = nextNode;
   }

   previous = current;
   current = next2nextNode;
  }
  /* Check for isolated node in pairs - when one node is left */
  if (current != null) {
   previous.next = current;
  }
  /* Return modified head of the list */
  return head;
 }

 /* Display data of nodes/iterate linked list */
 private static void displayLinkedList(Node head) {
  Node current = head;
  if (head != null) {
   System.out.print("[ ");
   while (current != null) {
    System.out.print(current.data + " ");
    current = current.next;
   }
   System.out.print(" ]");
  } else {
   System.out.println("Linked list is empty.");
  }

 }

 class Node {
  public int data;
  public Node next; // reference(handler) for next Node.

  public Node(int data) {
   this.data = data;
   this.next = null;
  }
 }

 public static void main(String[] args) {
  ReverseLinkedListElementsInPairs rpll = new ReverseLinkedListElementsInPairs();
  Node modifiedHead = null;
  System.out.println("------1st test-----");
  Node node1 = rpll.new Node(12);
  Node node2 = rpll.new Node(18);
  Node node3 = rpll.new Node(172);
  Node node4 = rpll.new Node(62);
  Node node5 = rpll.new Node(632);
  Node node6 = rpll.new Node(192);
  Node head = node1;
  node1.next = node2;
  node1.next.next = node3;
  node1.next.next.next = node4;
  node1.next.next.next.next = node5;
  node1.next.next.next.next.next = node6;
  System.out.println("Original list is:  12 18 172 62 632 192 19");
  System.out.print("Modified linked list is "
    + "(Using Iterative Implementation:) ");
  modifiedHead = rpll.reverseLinkedListInPairsIterative(head);
  displayLinkedList(modifiedHead);

  System.out.println("\n------2nd test-----");
  Node node12 = rpll.new Node(12);
  Node node22 = rpll.new Node(18);
  Node node32 = rpll.new Node(172);
  Node node42 = rpll.new Node(62);
  Node node52 = rpll.new Node(632);
  Node node62 = rpll.new Node(192);
  Node node72 = rpll.new Node(19);
  Node head2 = node12;
  node12.next = node22;
  node12.next.next = node32;
  node12.next.next.next = node42;
  node12.next.next.next.next = node52;
  node12.next.next.next.next.next = node62;
  node12.next.next.next.next.next.next = node72;
  System.out.println("Original list is:  12 18 172 62 632 192 19");
  System.out.print("Modified linked list is "
    + "(Using recursive Implementation:) ");
  modifiedHead = rpll.reverseLinkedListInPairsRecursive(head2);
  displayLinkedList(modifiedHead);
 }
}
==============Sample Output====================
 ------1st test-----
Original list is:  12 18 172 62 632 192 19
Modified linked list is (Using Iterative Implementation:) [ 18 12 62 172 192 632  ]
------2nd test-----
Original list is:  12 18 172 62 632 192 19
Modified linked list is (Using recursive Implementation:) [ 18 12 62 172 192 632 19  ]
=============================================
Tags:

1 Comments

Previous Post Next Post