Objective: Given a linked list and integer ‘k’, write an algorithm to reverse the linked list in groups of size ‘k’.
Example:
Approach:
- Earlier we have seen how to reverse a linked list, solution for reverse the linked list in groups of size will be extension of this solution.
- Reverse first ‘k’ nodes of the linked list, the kth node will be a new head, return it.
- Make a recursive call to rest of the list and attach it to the last node.(See the picture below)
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class ReverseInGrps { | |
public Node reveseGrps(Node head, int k){ | |
int x = k; | |
Node head_next=null; | |
Node h = head; | |
Node head_prev = null; | |
while(h!=null && x>0){ | |
head_next = h.next; | |
h.next = head_prev; | |
head_prev = h; | |
h = head_next; | |
x—; | |
} | |
if(head_next!=null){ | |
head.next = reveseGrps(head_next,k); | |
} | |
return head_prev; | |
} | |
public void display(Node head){ | |
Node n=head; | |
while(n!=null){ | |
System.out.print("->" + n.data); | |
n=n.next; | |
} | |
} | |
public static void main(String[] args) { | |
Node head = new Node(1); | |
head.next = new Node(2); | |
head.next.next = new Node(3); | |
head.next.next.next = new Node(4); | |
head.next.next.next.next = new Node(5); | |
head.next.next.next.next.next = new Node(6); | |
head.next.next.next.next.next.next = new Node(7); | |
head.next.next.next.next.next.next.next = new Node(8); | |
ReverseInGrps r = new ReverseInGrps(); | |
Node x = r.reveseGrps(head, 3); | |
r.display(x); | |
} | |
} | |
class Node{ | |
int data; | |
Node next; | |
public Node(int data){ | |
this.data = data; | |
} | |
} |
Output: ->3->2->1->6->5->4->8->7
Hi, this code wont work, if say i have a linked list like 1->2->3->4->5 ans i want to reverse in group of 3 nodes then it will return 3->2->1->5->4 which is not correct. Can you suggest me another approach where we get 3->2->1->4->5 only.Thanks.