旋转链表--巧转循环链表

0x01.问题

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
输入示例： 1->2->3->4->5->NULL, k = 2
输出示例：4->5->1->2->3->NULL
解释：
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

C++结构体：
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 C++函数形式：   ListNode* rotateRight(ListNode* head, int k)

0x02.详细分析

我们首先需要了解循环在这里的含义：

• 给定一个k，每个元素都往右边移动k个位置，如果移动到了表尾就转到表头去，始终不改变链表的大小。

为了方便得到解决的思路，我们可以看一个例子：

• 1->2->3->4->5->NULL k=2

移动完后的链表是下面这个例子：

• 4->5->1->2->3->NULL

发现很神奇的事情没有，我们可以看出，只要把第一个链表从4开始断开，然后重新做为表头，接到1的前面，是不是就完成了这样的旋转操作。

我们针对这一思路，开始去寻找相关的数据：

• 第一个：断开是从哪断开的。

从第一个例子可以看出，就是从尾部开始的第k个元素开始断开的，如果k=0，也就相当于没有断开，就是原链表。

但是还有一个情况，如果这个k大于了链表的长度会怎样呢？

我们可以看到这个链表的长度是5，如果旋转5次，那么又回到了原来的链表，旋转6次，就回到了原来旋转一次的样子，所以，我们可以发现这是一个循环的过程，也就是说，假设链表的长度是n，那么k的实际有效值就是 k%n ，这个很好理解，大于n后，就是跟之前的情况是一样的了。

注：图片来源Leetcode。

• 第二个，新链表的尾部。

其实也就是n-k%n-1的位置，就是断开的上一个元素。

于是我们有了一条思路了：

• 找到断开的位置，将链表断开，断开的后一部分成为新链表的头部，断开的前一部分成为新链表的下一部分，这样我们就可以产生整条新链表了。
• 这里还有个巧妙地办法，就是构建循环链表，我们可以把链表先接起来，也就是变成循环链表，然后再找到新的头，再把尾部断开，就构成了新的链表，这样可以省去不必要的遍历。

第一种方法的具体步骤：

• 遍历链表的得到n的值，也就是链表的长度。
• 再次遍历找到要断开的位置。
• 断开链表。
• 遍历到后一段尾部，让后一段的尾部与前一段的头部接起来。
• 返回后一段的头部，也就是新链表的头部。

第二种方法的具体步骤：

• 遍历到链表的尾部，同时得到链表的长度n。
• 将链表的尾部和头部接起来。
• 重新从原来头部遍历到断开的位置。
• 得到新头部。
• 断开头部前面的连接。

这里需要注意的是：

• 不能使用哑节点，因为会造成位置错误。

0x03.解决代码–循环链表

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head) return NULL;
        if(!head->next) return head;
        ListNode*oldtail=head;
        int n;
        for(n=1;oldtail->next;n++) oldtail=oldtail->next;
        oldtail->next=head;//成环
        ListNode*newtail=head;
        for(int i=0;i<n-k%n-1;i++) newtail=newtail->next;
        ListNode*newhead=newtail->next;
        newtail->next=NULL;//断环
        return newhead;
    }
};

ATFWUS --Writing By 2020–03–24