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); */
}
}
Advertisements
