Given a linked list, rotate the list to the right by k
places.
// 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
Here's the solution:
public ListNode rotateRight(ListNode head, int k) {
if(head == null || k == 0){
return head;
}
int len = 0;
ListNode temp = head;
// get the list length
while(temp != null){
temp = temp.next;
len++;
}
// make sure rotating steps not exceeding list length
k = k % len;
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
ListNode tail = dummy;
// move k steps from head
for(int i = 0; i < k; i++){
head = head.next;
}
// move both head and tail forward until last node is reached
while(head.next != null){
head = head.next;
tail = tail.next;
}
// connect the nodes
head.next = dummy.next;
dummy.next = tail.next;
tail.next = null;
return dummy.next;
}
Here's some visual graphs for better understanding.
With the aid of visual graphic, is it better to understand linked list operation now? Hope you enjoy this post! See ya!
Post was published on , last updated on .
Like the content? Support the author by paypal.me!