Given the head of a linked list, rotate the list to the right by k places.
Example 1:
Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3]
Example 2:
Input: head = [0,1,2], k = 4 Output: [2,0,1]
Constraints:
[0, 500].-100 <= Node.val <= 1000 <= k <= 2 * 109/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (k == 0 || head == null || head.next == null)
return head;
ListNode marker = head, curr = head;
int count = 0;
while (curr != null && count++ <= k)
curr = curr.next;
if (count <= k) { // i.e., has not crossed k
k %= count;
if (k == 0)
return head;
curr = head;
count = 0;
while (curr != null && count++ <= k)
curr = curr.next;
}
while (curr != null) {
curr = curr.next;
marker = marker.next;
count++;
}
ListNode newHead = marker.next;
marker.next = null;
curr = newHead;
while (curr.next != null)
curr = curr.next;
curr.next = head;
return newHead;
}
}