Day77 | 灵神 | 反转链表 反转链表 反转链表II K个一组翻转链表

206.反转链表

206. 反转链表 - 力扣（LeetCode）

思路：

笔者之前做过所以做的很快，简单来说用p指向现在的结点，pre指向p的前一个节点，用指向p的下一个节点

然后就是让p->next指向前一个节点pre，这是反转

再让前一个结点变成p，p变成q，这是往后继续遍历

也可以看灵神的视频讲解，有图示很快理解

反转链表【基础算法精讲 06】_哔哩哔哩_bilibili

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *p=head;
        ListNode *pre=nullptr;
        while(p!=nullptr)
        {
            ListNode* q=p->next;
            p->next=pre;
            pre=p;
            p=q;
        }
        return pre;
    }
};

92.反转链表II

92. 反转链表 II - 力扣（LeetCode）

思路：

这道题和上一题的区别就是在反转完链表以后，需要把反转的部分[2,3,4]接到这一段的前一个结点1和后一个节点5，如下图所示

image-20250330120115364

所以我们就保存一下反转这段的前一个节点1，图中的p0，笔者用lpre表示，而后一个节点不需要保存，因为遍历结束的时候就是cur所指的，cur就是笔者的p指针，pre就是pre

所以反转结束后，把pre接到lpre后面

链表反转部分的第一个结点2反转后变成最后一个结点，把cur和2连上就构成了新的链表，然后返回头结点head就行

可是有一个问题

如果反转的部分不是2,3，4而是1,2,3呢，即left==1的情况？

那lpre不就不存在了嘛？

所以就需要建立一个虚拟头结点，只要建立一个虚拟头结点，那么所有的反转的情况都不可能是第一个节点开始，而我们要做的就是按照上面的思路按部就班就好了

完整代码：

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
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        //虚拟头结点
        ListNode res(0,head);
        //反转部分的第一个节点
        ListNode* l=&res;
        //图中的p0，反转部分的前一个节点
        ListNode* lpre=&res;
        //找需要反转的部分
        for(int i=0;i<left;i++)
        {
            if(i<left-1)
                lpre=lpre->next;
            l=l->next;
        }
        //反转链表
        ListNode *p=l;
        ListNode *pre=nullptr;
        for(int i=0;i<right-left+1;i++)
        {
            ListNode* q=p->next;
            p->next=pre;
            pre=p;
            p=q;
        }
        //将反转的这段给接到原来链表
        lpre->next=pre;
        l->next=p;
        //返回结果
        return res.next;   
    }
};

25.K个一组翻转链表

25. K 个一组翻转链表 - 力扣（LeetCode）

思路：

这道题和上一道题基本上没什么区别，就是上一道题是只需要反转一次，而这一道题需要反转多次，而每一次反转都需要让left和right增加k，并且left和right的间隔永远是k

上一道题是反转一次，我们保存了lpre，即left的上一个节点

那这道题是多次反转，那说明我们每次反转前都需要保存或者说更新left的上一个节点，以保证我们的链表可以是连起来，这里如果想不通的话记得去看看图示或者自己动手画一画

图示请看灵神的视频

反转链表【基础算法精讲 06】_哔哩哔哩_bilibili

完整代码：

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
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        //建立虚拟头结点 因为第一个left肯定是1，第一个right肯定是k，根据上一题可以知道，left是1的时候要建立一个虚拟头结点
        ListNode res(0,head);
        ListNode* cnt=res.next;
        //统计链表长度
        int length=0;
        while(cnt!=nullptr)
        {
            length++;
            cnt=cnt->next;
        }
        //开始反转
        ListNode* p=head;
        ListNode* pre=nullptr;
        ListNode* lpre=&res;
        //一共反转length/k下取整次
        for (; length >= k; length -= k)
        {
            for(int i=0;i<k;i++)
            {
                //普通的反转
                ListNode* q=p->next;
                p->next=pre;
                pre=p;
                p=q;
            }
            //让链表连接起来 同时更新lpre
            ListNode* nxt=lpre->next;
            lpre->next->next=p;
            lpre->next=pre;
            lpre=nxt;
        }
        //返回结果
        return res.next;
    }
};