【leetcode】61 Rotate List

描述

链表右移动 k 位

样例

样例1

输入: [1,2,3]  k = 2
输出: [2,3,1]

样例2

输入: [1,2,3,4,5], 2
输出: [4,5,1,2,3]

思路

把序列多写几个 1 2 3 1 2 3 1 2 3
假设我们现在在这里 .

我们可以向左和向右移动，左移动 k 位 = 右移动 len - k 位 ，len 代表链表的长度

代码

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        // for NULL list
        if(!head){return head;}
        // the len of list
        int len = 1;
        // get the tail node of the list
        ListNode * tail = head;
        ListNode * p = head;
        while(tail->next){ tail = tail->next; len++;}
        // connect the tail and head 
        tail -> next = head;
        // think about 3 node about 1 2 3
        // 1 2 3   1 2 3   1 2 3
        // 0 1 2   3 4 5   6 7 8
        // supose we are at in index 3, and now k = 2
        // we can just left move to index = 3-2 = 1
        // also we can right move len - k = 3-2 = 1 ,and move 1 ,new we are in index = index+1 = 4 
        k = len - k%len;  // this is for k > len
        while(k--){ p=p->next;}
        head = p;  // we found the new head
        len--;
        while(len--){p=p->next;}// we found the new tail
        p->next = NULL;
        return head;
    }
};

参考

原题链接

---