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)