Rotate Linked List with javascript (LEET CODE)
Sumit Joshi
Posted on October 5, 2020
Problem:-
Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
Algorithm:-
Step 1 :- First we will find the length of linked list by traversing through it.
step 2:- after traversing through linked list we are at tail node
step 3:- connect tail node to head node
step 4 :- comparing the length of linked list with passed rotation value(k)
step 5:- after comaring it with k we will get new length to get new rotated linked list
SOLUTION:-
var rotateRight = function(head, k) {
if(head == null || k == 0){
return head
}
let i = 1
let tail =head
while(tail.next != null){
i++
tail =tail.next
} //i = 5(length of list)
if(k == i){
return head
}
while(k > i){
k = k - i
}
let j = i-k // j = 5-2
tail.next =head;
let newTail = tail;
while(j-- > 0){
newTail = newTail.next
}
let newHead = newTail.next
newTail.next = null;
return newHead
};
Posted on October 5, 2020
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
November 29, 2024