61. Rotate List

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

---

这一题要把链表的后k个右旋到开头，其实就是把后k个节点断开，然后接到开头。思路是先遍历一遍得到链表长度n，然后k=k%n。再从头开始找第n-k-1个，断开然后拼接到开头即可。 完整代码如下：

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k)
    {
        if (head == NULL || head->next == NULL || k == 0)
            return head;
        int n = 1, cut_pos = 0;
        ListNode* tail = head;
        while (tail->next != NULL) {
            n++;
            tail = tail->next;
        }
        //while (k >= n)k -= n;
        k = k % n;
        if (k == 0)
            return head;
        ListNode* new_tail = head;
        while (cut_pos + k + 1 < n) {
            new_tail = new_tail->next;
            cut_pos++;
        }
        ListNode* new_head = new_tail->next;
        new_tail->next = NULL;
        tail->next = head;
        return new_head;
    }
};

本代码提交AC，用时20MS。

还可以其他一些思路，比如把连接头尾相连成一个环，然后找到断开的位置；或者使用快慢指针找到需要断开的位置，快指针先走k步，慢指针再从头开始走，当快指针到末尾时，慢指针就到断开位置了。其实吧，我觉得直接找第n-k-1的位置，应该不比快慢指针慢吧，不知道为什么我这个花了20MS。

二刷。思路跟之前的一样，代码更好看一点。

class Solution {
public:
	int GetListLength(ListNode* head) {
		int len = 0;
		while (head) {
			++len;
			head = head->next;
		}
		return len;
	}
	ListNode* rotateRight(ListNode* head, int k) {
		int len = GetListLength(head);
		if (len == 0 || len == 1)return head;
		k = k % len;
		if (k == 0)return head;
		int l = len - k;
		ListNode *first = head;
		while (--l) { // 注意是--l，不是l--，停在断开前一个位置
			first = first->next;
		}
		ListNode *second = first->next;
		first->next = NULL;
		first = second;
		while (first->next)first = first->next;
		first->next = head;
		return second;
	}
};

本代码提交AC，用时8MS。