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

Fig 1: Reverse singly linked list in pairs

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

single linked list pair reverse — Fig 3: Pairwise swap of nodes

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 

Example – reverse singly linked list in pairs using java.

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

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

1.) ReverseLinkedListInPair Class:

2.) DemoLinkedListInPairs Class:

3.) Node Class:

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

You may also like: