Can you rotate a Linked List by k places?
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!