Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
Thoughts
右移k位先mod n, 确定实际是右移多少位。k == 0时直接返回head. 前面n - k 个不动，把后面k个移到前面，再把前面n - k个贴到后面。或者和rm n the node一样也是从后数k个，因此想到俩指针先后走解法。
Code
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
int n = 0;
auto cur = head;
while (cur != nullptr) {
++n;
cur = cur->next;
}
if (!n) return head;
k = k % n;
if (k == 0) return head;
cur = head;
for (int i = 0; i < n - k - 1; ++i) {
cur = cur->next;
}
auto new_head = cur->next;
cur->next = nullptr;
cur = new_head;
while (cur->next != nullptr) {
cur = cur->next;
}
cur->next = head;
return new_head;
}
};
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
private int getLen(ListNode head) {
int len = 0;
while (head != null) {
len++;
head = head.next;
}
return len;
}
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
int len = getLen(head);
k = k % len;
ListNode first = head, sec = head;
for (int i = 0; i < k; i++) {
first = first.next;
}
if (first == null) {
return head;
}
while (first != null && first.next != null) {
first = first.next;
sec = sec.next;
}
ListNode last = first;
last.next = head;
head = sec.next;
sec.next = null;
return head;
}
}