Home » Link Lists(Nuts & Bolts of CS) » Reverse in Pair

Reverse in Pair

Given a linked list, write a function to reverse every k nodes (where k is an input to the function).

Example:
Inputs: 1->2->3->4->5->6->7->8->NULL and k = 3
Output: 3->2->1->6->5->4->8->7->NULL.

Inputs: 1->2->3->4->5->6->7->80->NULL and k = 5
Output: 5->4->3->2->1->8->7->6->NULL.

Algorithm: reverse(head, k)
1) Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be next and pointer to the previous node be prev.
2) head->next = reverse(next, k) /* Recursively call for rest of the list and link the two sub-lists */
3) return prev /* prev becomes the new head of the list (see the diagrams of iterative method of this post) *

class ReversePair
{
 static class Node
 {
 int data;
 Node next;

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


 public static Node head = null;
public void reversePairRecursive(Node n)
{
 int temp;
 if(n==null || n.next ==null)
 return; //base case for empty or 1 element list
 else
 {

 // its just swapping
 //Reverse first pair
 temp = n.data;
 n.data = n.next.data;
 n.next.data = temp;

//Call the method recursively for the rest of the list
 reversePairRecursive(n.next.next);
 }

}
/**
* Reverse the linkedlist in pairs -Iterative version
* @param n
*/
public void reversePairIterative()
{
 Node current = head;
 int temp;

while(current != null && current.next != null)
 {
 //Swap the pair
 temp = current.data;
 current.data = current.next.data;
 current.next.data= temp;

//Advance the current pointer twice
 current = current.next.next;
 }
}

 
private void push(int data)
 {
 Node newnode= new Node(data);
 newnode.next = head;
 head = newnode;

}

 public void printList(Node node)
 {
 while (node != null)
 {
 System.out.println(node.data);
 node = node.next;
 }
 }


 public static void main(String args[])
 {
 ReversePair kll = new ReversePair();
 kll.push(8);
 kll.push(7);
 kll.push(6);
 kll.push(5);
 kll.push(4);
 kll.push(3);
 kll.push(2);
 kll.push(1);

kll.printList(kll.head);

 kll.reversePairRecursive(kll.head);
 System.out.println("===========================");
 kll.printList(head);

 /* for iterative case.........
 kll.printList(kll.head);
 kll.reversePairIterative();
 System.out.println("===========================");
 kll.printList(head); */
 }
}


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: