# Question

Formatted question description: https://leetcode.ca/all/61.html

61	Rotate List

Given a 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

First traverse the original linked list to get the length n of the linked list, and then take the remainder of k to n, so that k must be less than n.

Use the fast and slow pointers to solve, the fast pointer first walks k steps, and then the two pointers go together, when the fast pointer reaches the end , The next position of the slow pointer is the head node of the new order, so that the linked list can be rotated.

# Code

Java

• 
public class Rotate_List {

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode rotateRight(ListNode head, int k) {

}

// k could be larger than list-length
int length = 0;
while (p != null) {
length++;
p = p.next;
}

// avoid circle rotate
k = k % length;

if (k == 0) {
}

// two pointers, j is k behind i
while (k > 0) {
i = i.next;
k--;
}

while (i.next != null) { // i will stop at last node, j will stop at after-rotate end node

i = i.next;
j = j.next;
}

ListNode newHead = j.next; // @note: here, hidden assumption is "j.next != null” . eg: input: list=, k=0
j.next = null; // cut

}

}

public class Solution_make_circle {

public ListNode rotateRight(ListNode head, int n) {

if (head == null || head.next == null || n == 0)

// compare list length with k, what if k is extremely large
int count = 1;
while (ptail.next != null) {
count++;
ptail = ptail.next;
}

int cutoff = count - (n % count);

ptail.next = head; // @note: connect head tail, making it circular list

for (int i = 0; i < cutoff; i++) {
ptail = ptail.next;
}

ptail.next = null;
}
}

}

• // OJ: https://leetcode.com/problems/rotate-list/
// Time: O(N)
// Space: O(1)
class Solution {
int ans = 0;
return ans;
}
public:
ListNode* rotateRight(ListNode* head, int k) {
k %= len;
if (k == 0) return head;
while (k--) q = q->next;
while (q->next) p = p->next, q = q->next;
auto ans = p->next;
p->next = nullptr;
return ans;
}
};

• # Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:type k: int
:rtype: ListNode
"""
l = 1
while p.next:
l += 1
p = p.next
k = k % l
if k == 0:
k = l - k % l - 1
print
k
while k > 0:
pp = pp.next
k -= 1