LeetCode 61. Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

Example:

Given 1->2->3->4->5->NULL and k = 2,

return 4->5->1->2->3->NULL.

 

---

 

 

本来以为是一道很简单的旋转链表的题目，但是写出来之后漏洞百出，要考虑的特殊情况很多，比如k=0，head为null，k远远超过链表长度的情况。最大的感悟：做leetcode一定要学正确的思路，然后一遍遍强化；错误总是无穷无尽，你不能在一遍遍试错中学习，因为这么做太慢了。

言归正传，最直接的思路是用两个指针，第一个先走k步，然后两个一起走，注意一定要考虑特殊情况

代码如下：

class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        if (!head) return NULL;
        int n = 0;
        ListNode *cur = head;
        while (cur) {
            ++n;
            cur = cur->next;
        }
        k %= n;
        ListNode *fast = head, *slow = head;
        for (int i = 0; i < k; ++i) {
         fast = fast->next;
        }
        while (fast->next) {
            fast = fast->next;
            slow = slow->next;
        }
        fast->next = head;
        fast = slow->next;
        slow->next = NULL;
        return fast;
/*
以上四行也可以这么写，但是当k=0,链表只有一个元素时会出错
 ListNode *t = slow->next;
        slow->next = NULL;
        fast->next = head;
        fast = slow->next;
*/
    }
};

另一种方法更加直观一些，只遍历一遍链表，得到链表长之后收尾连接，在前进 n - n%k得到新的链表头

代码如下：

class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        if (!head) return NULL;
        int n = 1;
        ListNode *cur = head;
        while (cur->next) {
            ++n;
            cur = cur->next;
        }
        cur->next = head;
        int m = n - k % n;
        for (int i = 0; i < m; ++i) {
            cur = cur->next;
        }
        ListNode *newhead = cur->next;
        cur->next = NULL;
        return newhead;
    }
};