Sitch's Blog
0%

LeetCode-No-61

发表于 分类于 Valine：

旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 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

示例 2:

输入: 0-1-2-NULL, k = 4 输出: 2-0-1-NULL 解释: 向右旋转 1 步: 2-0-1-NULL 向右旋转 2 步: 1-2-0-NULL 向右旋转 3 步: 0-1-2-NULL 向右旋转 4 步: 2-0-1-NULL

题目分析

1. 直观移位——每个节点向右移动K位

遍历每个节点，都后向计算出该位置的新节点，即向左找K位，然后赋值过来。思路很简单。 （前向计算也是可以的，甚至更利于想出优化的第二步） ##### 注意细节：一个是移动出了链头，要转到链尾继续移动。 ##### 然而链表头并没有指向链尾的指针，因此怎么从链头转到链尾呢？ 一个很傻的方法是把链表数值做成vector...然后在vector中找相应的数值，然后赋给当前位置... 很傻，浪费空间时间= = ##### 2. 我们的目标是从链头转到链尾，然而链头唯一的跳转指针next又必须连着链表，所以不太好修改头指针。但是链尾的next是空的，我们是不是可以利于一下呢？ 再看前向计算，每个节点向右移动K位，找到正确位置然后赋值，问题也在于怎么从链尾转移到链头。 ##### 3. 因此我们可以把链尾连向链头，即tail-next=head，此时找位置的问题就不存在了，可以开开心心对每个节点遍历。 ##### 4. 遍历移动完想想，移完虽然AC了，但好像憨憨的？链表顺序还是原来的样子，对链尾连着链头的循环链表来讲，移完看起来只不过是head从原节点，往前走了几步，然后停了下来选了一个新位置当head。 例如 1-2-3-4-5，k=2 遍历移动==》4-5-1-2-3，即head往前走了K步，停在了4的位置，然后以4为链头往后即是新链表。 ##### 5. 因此我们不需要遍历移动每个节点，首先我们找到链尾，然后知道链尾往前K个（包括链尾本身）即是新head，找到新head时，把head前一个的next置为NULL，断开循环链表即是所需链表。 当然，我们在链尾的时候同样不能往前走，因此往前找K个即相当于往后找L-K+1个（不包括链尾）。 你可能会想既然是从链尾向后找L-K+1个，那不是相当于从最初的head过去找L-K个吗？

但是没有先遍历到链尾，把链尾链头连接起来的话，我们是没有循环链表的，即使一开始从head找出新head，我们还是得再遍历到链尾，连上链头，再把新链头和新链尾断开= = 当然直接从head开始找，可以沿途把新链尾和原链头都存储下来，然后遍历到链尾的时候，该连的连该断的断即可= =。

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) 
    {
        ListNode* i=head;
        int L=0;
        if(head==NULL)
            return head;
        
        while(i-next!=NULL)//找链尾
        {

            i=i-next;
            L++;
        }
        L++;

        i-next=head;//首尾相连
        //缩小k
        k%=L;
        int j=0;
        //从末尾起移动L-k到达 i , i-next是新头
        k=L-k;

        while(j<k)
        {
            i=i-next;
            j++;
        }

        head=i-next;
        i-next=NULL;

       

       return head;
    }
};