Reverse singly linked List in pairs in java (example / non-recursive)

• Given a single linked list, we would like to reverse a single linked list in pairs.
• We would like to reverse the nodes in pair (swap the references of alternate nodes).

Example – reverse singly linked list in pairs using java.

Reverse singly linked list in pairs (refer Fig 1)

• Swap Node 10 and 20 of single linked list.
  • Node 20 will become head of single linked list.
  • Node 10 become second node of single linked list.
• Swap Node 30 and 40
  • Node become third node of a single linked list.
  • Node 30 become fourth node of a single linked list
• Node 50 will be last node in linked list
• Singly linked list is reversed in pairs, as shown in a Fig 2.

• We can simply swap the data of nodes instead of swapping the references.
• Just for better understanding, we are swapping the references of node.
  • It will give better insight of problem statement.
  • So, we will use the swapping of references in our problem statement.

Algorithm: reverse single linked list in pairs in java (non recursive)

• Take prev pointer pointing at head of single linked list
• Store the reference of second node of single linked list
  • As second node will become the new head of single linked list (Fig 2).
• temp reference pointing to next of head
  • temp start pointing to Node 20
• Break the link between Node 10 and Node 20
  • Set head.next to temp.next
    • Node 10 start pointing to Node 30
• Set up the link between Node 20 to Node 10
  • Set temp.next to head
    • Node 20 start pointing to Node 10
      • Node 20 will be new head of linked list
• Store the prev reference
  • Which will be useful for next iteration
• We will follow the above procedure for rest of nodes
  • Single linked list will be reversed in pairs. (Refer Fig 3)

Time complexity of algorithm is O (n).

Program – reverse single linked list in pairs using iterative algorithm in java.

1.) ReverseLinkedListInPair Class:

• We are passing the head of single linked list to ReverseLinkedListInPair class.
• We will reverse singly linked list in pairs.

package org.learn.Question;

import org.learn.List.Node;

public class ReverseLinkedListInPair {

 public static Node reverseLinkedListInPair(Node head) {

  Node prev = head;
  Node newHead = head.next;
  Node temp = head.next;

  while (head != null && head.next != null) {
   
   prev.next = head.next;
   head.next = temp.next;
   temp.next = head;
   
   if (head.next != null) {
    prev = head;
    head = head.next;
    temp = head.next;
   }
  }

  return newHead;
 }

 public static void insert(Node head, int data) {

  while (head.next != null)
   head = head.next;
  head.next = new Node(data);
 }

 public static void print(Node head) {

  while (head != null) {
   System.out.printf("%d ", head.data);
   head = head.next;
  }

  System.out.println("");
 }
}

2.) DemoLinkedListInPairs Class:

• We are creating the single linked list in main method.
• We are calling ReverseLinkedListInPair.reverseLinkedListInPair method, to reverse single linked list in pairs.

package org.learn.Client;

import org.learn.List.Node;
import org.learn.Question.ReverseLinkedListInPair;

public class DemoLinkedListInPairs {
 
 public static void main(String[] args) {
  
  int[] data = { 10, 20, 30, 40, 50 };
  Node head = new Node(data[0]);
  
  for (int count = 1; count < data.length; count++) {
   ReverseLinkedListInPair.insert(head, data[count]);
  }
  
  System.out.printf("1. Single linked list is : ");
  ReverseLinkedListInPair.print(head);

  System.out.printf("2. Reverse single linked list in pairs : ");
  head = ReverseLinkedListInPair.reverseLinkedListInPair(head);
  ReverseLinkedListInPair.print(head);
 }
}

3.) Node Class:

• Node class is representing the nodes of a single linked list

package org.learn.List;

public class Node {
 public int data;
 public Node next;

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

Output – reverse singly linked List in pairs in java (iterative)

1. Single linked list is : 10 20 30 40 50 
2. Reverse single linked list in pairs : 20 10 40 30 50 

Download Code – reverse linked List in pairs (non-recursive)