Reverse a Linked List in groups of given size using Javascript
In this post given a linked list, write a function to Reverse a Linked List in groups of given size using Javascript after every k nodes (where k is an input to the function).
Input: 1->2->3->4->5->6->7->8->NULL, K = 3
Output: 3->2->1->6->5->4->8->7->NULLInput: 1->2->3->4->5->6->7->8->NULL, K = 5
Output: 5->4->3->2->1->8->7->6->NULL
To reverse a linked list you can check : Reverse Linked List in Javascript
- 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.
- head->next = reverse(next, k) ( Recursively call for rest of the list and link the two sub-lists )
- Return prev ( prev becomes the new head of the list).
class Node {
constructor(value) {
this.data = value;
this.next = null;
}
}
class LinkedList {
constructor(head = null) {
this.head = head;
}
add(value) {
let node = new Node(value)
if (this.head == null)
this.head = node;
else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
}
rotateByK(K, head = this.head ){
let current = head;
let next = null;
let prev = null;
let i = 0;
while(i < K && current != null){
next = current.next;
current.next = prev;
prev = current;
current = next;
i++;
}
if(next != null)
head.next = this.rotateByK(K,next);
return prev;
}
}
let ll = new LinkedList();
ll.add(10);
ll.add(20);
ll.add(30);
ll.add(40);
ll.add(50);
ll.add(60);
ll.add(70);
let rotateK = ll.rotateByK(3);
console.log(JSON.stringify(rotateK))References :
https://www.geeksforgeeks.org/reverse-a-list-in-groups-of-given-size/
