Rotate a Linked List in Javascript
In this post we are going to Rotate a Linked List in Javascript . For example, if the given linked list is 10->20->30->40->50->60 and k is 4, the list should be modified to 50->60->10->20->30->40. Assume that k is smaller than the count of nodes in linked list.
To create a linked list please check my previous post : Create Linked List in Javascript
To rotate the linked list, we need to change next of kth node to NULL, next of the last node to the previous head node, and finally, change head to (k+1)th node. So we need to get hold of three nodes: kth node, (k+1)th node and last node.
Traverse the list from the beginning and stop at kth node. Store pointer to kth node. We can get (k+1)th node using kthNode->next. Keep traversing till the end and store pointer to last node also. Finally, change pointers as stated above.
Lets see the program below
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;
}
}
rotate(k) {
let previousHead = this.head,
previous = this.head,
current = this.head;
let i = 1;
while(current.next){
if(i == k+1){
this.head = current;
previous.next = null;
}
previous = current;
current = current.next;
i++;
}
current.next = previousHead;
return this;
}
}
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 rotate = ll.rotate(3);
console.log(JSON.stringify(rotate))
