[TOC]

前言，CSDN的小问题😥

最近写博客的时候，发现CSDN的markdown语法不支持加粗一句话末尾的标点符号

1
2
**你好呀，**
**你好呀**，

这两种方式在typora上都会加粗（包括末尾的标点）

但是在CSDN上，第一种情况会显示出markdown源码，无法加粗

你好呀，我是你的好朋友
你好呀，我是你的好朋友

虽然这不是什么大事，但有的时候写博客，一句本来应该是加粗的话，多显示了几个**，不太美观，还会给不了解markdown的读者带来困扰：“作者在这里打几个*号是干嘛？”

上一篇博客，我们学习了单向无头非循环链表，本篇博客就让我们实践一下，刷十道leetcode的链表OJ题目吧🌭

如果你把本篇博客里的这几道题都弄明白了，那说明你对链表的掌握已经非常棒了！加油！

话不多说，直接进入今天的正题！

第一题：206.反转链表

leetcode：206. 反转链表

题目需要我们把1-2-3-4-5的链表反转为5-4-3-2-1的链表

有一种取巧的办法，是将所有数取出来放入一个数组，再倒着将数组里面的数放回去

这种办法可以通过OJ，因为leetcode并没有检查返回链表的地址。但并不符合题目的真正要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct ListNode* reverseList(struct ListNode* head){

    struct ListNode* newhead=NULL;
    struct ListNode* cur=head;
    while(cur)
    {
        struct ListNode* next=cur->next;
        cur->next=newhead;

        newhead=cur;
        cur=next;
    }


    return newhead;
}

image-20220324134813384

相同思路的c++代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        ListNode* prv = nullptr;
        ListNode* cur = head;
        while(cur->next != nullptr){
            // 先记录下下一个节点
            ListNode* next = cur->next;
            // 当前节点链接上一个节点
            cur->next = prv;
            // 更新上一个节点和当前节点
            prv = cur;
            cur = next;
        }
        // cur->next为空了代表走到了原始链表的末尾了
        cur->next = prv;
        return cur;
    }
};

第二题：876.链表的中间节点

LeetCode： 876. 链表的中间结点

image-20220324131145518

这道题目需要我们返回单链表的中间节点

如果链表节点个数是奇数，返回中间节点；

如果链表节点个数是偶数，返回第二个节点。

  • 对于数组和顺序表来说，我们只需要利用下标直接访问中间节点即可
  • 对于单链表来说，我们不知道它究竟有多少个节点，即便知道了，也需要通过遍历的方法找到这个中间节点

这道题我想出了两种解题方式

解法一：遍历

通过遍历得出该链表的节点个数，再使用一个新的指针，查找中间节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct ListNode* middleNode(struct ListNode* head){
    if(head==NULL)
        return NULL;

    int count=1;//计算链表一共的节点数
    struct ListNode* tail=head;//找尾
    while(tail->next!=NULL)
    {
        tail=tail->next;
        count++;
    }
    int half=(count/2); 
    //如果是3结果为1，如果是4结果为2
    //正好是从head开始寻找的次数
    struct ListNode* mid =head;
    while((mid->next!=NULL)&&(half--))
    {
        mid=mid->next;
    }

    return mid;
}

对于链表oj题目，leetcode会把这个链表的形式以注释的方式标注在最前面

image-20220324131831982

解法二：快慢指针（很爽👍）

image-20220324134027858

这种方法实现起来也很是简洁，也击败了更多用户！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct ListNode* middleNode(struct ListNode* head){
    if(head==NULL)
        return NULL;

    struct ListNode*fast=head;
    struct ListNode*slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }

    return slow;
}

image-20220324134130360

第三题：OR36 链表的回文结构👨‍🔧

牛客网：OR36 链表的回文结构

image-20220324135026202

这道题我们可以使用一个很特别的方法

  • 先找到这串链表的中间节点（可以用到876里的函数）

  • 再将这个节点之后的链表逆置（206反转链表）

1
2
3
1-2-3-2-1
//逆置后
1-2-1-2-3

需要注意的是，逆置函数并不会改变第一个2的next节点，它依旧是链接在3上的

1
2
3
//进行遍历判断
1-2-(3)
1-2-3

这样我们就能判断出该链表是否为回文结构了！

开始敲代码，发现牛客网上只有C++的选项，没有C语言

image-20220324183135738

实际上，C++编译器都是支持C语言的，我们可以直接在题目给出的C++结构下进行C语言代码的编写

题目要求的返回值是一个bool类型。如果你不了解它，布尔类型是C99引入的，简单的来说，ture代表1，false代表0

  • 在之前的博客中我写到过这个类型👉点我
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class PalindromeList {
public:
    //链表逆置
    struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* newhead = NULL;
        struct ListNode* cur = head;
        while (cur)
        {
            struct ListNode* next = cur->next;
            cur->next = newhead;

            newhead = cur;
            cur = next;
        }
        return newhead;
    }
    //中间节点返回
    //1 2 3 4  偶数个，返回3
    //1 2 3    奇数个，返回2
    struct ListNode* middleNode(struct ListNode* head) {
        if (head == NULL)
            return NULL;


        int count = 1;//计算链表一共的节点数
        struct ListNode* tail = head;//找尾
        while (tail->next != NULL)
        {
            tail = tail->next;
            count++;
        }
        int half = (count / 2);
        //如果是3结果为1，如果是4结果为2
        //正好是需要从head开始寻找的次数
        struct ListNode* mid = head;
        while ((mid->next != NULL) && (half--))
        {
            mid = mid->next;
        }

        return mid;
    }

    bool chkPalindrome(ListNode* A) {
        struct ListNode* mid = middleNode(A);
        struct ListNode* ret = reverseList(mid);
        //1 2 3 2 1 回文链表
        //先逆转后面3个
        //1 2 1 2 3
        //这时候第一个2存放的next依旧是下一个3的地址
        //使用while循环进行判断，都是判断3次是否相等
        //相等就是回文，否则不是
        while (A && ret)
        {
            if (A->val == ret->val)
            {
                A = A->next;
                ret = ret->next;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
};

image-20220324183727271

第四题：链表中倒数第K个节点

牛客网：链表中倒数第k个结点

image-20220324184135923

这道题我们同样可以使用快慢指针来解决

倒数第k个节点，就需要快指针先走k步

这里我尝试用PS做了一个动图，给大伙瞅瞅

链表倒数第k个节点

这道题也是只有C++选项。和上道题一样，我们直接在C++下编写C语言代码就可以了

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
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if (pListHead == NULL)
            return NULL;
        
        struct ListNode* fast = pListHead;
        struct ListNode* slow = pListHead;

        int i = k;
        while (i--)
        {
            if (fast == NULL)
            {
                return NULL;
            }
            fast = fast->next;
        }


        while (fast)
        {
            fast = fast->next;
            slow = slow->next;
        }

        return slow;
    }
};

image-20220324191901610

第五题：CM11 链表分割

牛客网：CM11 链表分割

image-20220324192644496

这道题我使用了带头节点的做法，head->next等同于不带头链表的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
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
    if(pHead==NULL)
        return NULL;
        
    struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode));//新链表-比x小的部分
    struct ListNode* Bigger=(struct ListNode*)malloc(sizeof(struct ListNode));//比x大的部分
        
    //这里需要定义一个新的指针来遍历链表，防止找不到头
    struct ListNode* head=newhead;
    struct ListNode* big=Bigger;
    
    while(pHead)
    {//遍历里面比x小的，链接在newhead上
        if(pHead->val  <x)
        {
            head->next=pHead;
            pHead=pHead->next;
            head=head->next;
            
        }
        else
        {//比x大的链接在bigger上
            big->next=pHead;
            pHead=pHead->next;
            big=big->next;
        }
    }
    big->next=NULL;//big的末尾需要置空
    head->next=Bigger->next;//让head的末尾链接bigger的头部
        
    struct ListNode* list=newhead->next;
    free(newhead);
    free(Bigger);
    return list;
    }
};

image-20220324192852926

第六题：21. 合并两个有序链表

leetcode：21. 合并两个有序链表

image-20220324192148193

这道题的解析就放注释啦

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
47
48
49
50
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1==NULL)
        return list2;
    if(list2==NULL)
        return list1;

    struct ListNode* H1=list1;
    struct ListNode* H2=list2;
    struct ListNode* newList=NULL;
    struct ListNode* tail=NULL;
    if(H1->val<H2->val)//选取新链表的第一个节点
    {
        newList=H1;
        tail=H1;
        H1=H1->next;
    }
    else
    {
        newList=H2;
        tail=H2;
        H2=H2->next;
    }


    while(H1 && H2)//其中一个走完了，就退出循环
    {
        if(H1->val<H2->val)//找小的那一个链接在尾部
        {

            tail->next=H1;
            tail=H1;//等同于tail=tail->next
            H1=H1->next;
        }
        else
        {
            tail->next=H2;
            tail=H2;//等同于tail=tail->next
            H2=H2->next;
        }
    }
//最后结束了，还需要判断是谁走完了，把另外一个链表剩下的部分链接在尾部
//链表本身是有序的，所以最后无需再进行排序，直接链接即可
    if(H1)
        tail->next=H1;

    if(H2)
        tail->next=H2;
    
    return newList;
}

image-20220324192251756

第七题：160.相交链表

leetcode：160. 相交链表

image-20220324193452619

题目需要我们返回两个相交链表的交点c1，如果不相交就返回NULL。

最后一行还提到了，这道题不能破坏原始链表

本题思路如下：

  • 先用两个指针，分别遍历A、B链表，得到两个链表长度
  • 遍历完毕时，指针处在末尾C3，如果末尾不相等，就说明该链表不相交，返回NULL
  • 如果相等，计算出A、B链表的长度差，使用快慢指针进行操作
  • 快指针从长链表开始走，先走|A-B|长度。然后慢指针也开始移动，直到它们相交

链表相交

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
47
48
49
50
51
52
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if((headA==NULL)||(headB==NULL))
        return NULL;

    int countA=1;
    int countB=1;
    struct ListNode *HA=headA;
    struct ListNode *HB=headB;
    while(HA&&HA->next)
    {
        countA++;
        HA=HA->next;
    }
    while(HB&&HB->next)
    {
        countB++;
        HB=HB->next;
    }

    if(HB!=HA)//结尾不相等，说明不相交
        return NULL;

    int num=abs(countA-countB);
    struct ListNode* fast=NULL;
    struct ListNode* slow=NULL;
    if(countA>countB)
    {
        fast=headA;
        slow=headB;
    }
    else
    {
        fast=headB;
        slow=headA;
    }

    while(num--)//fast先走
    {
        fast=fast->next;
    }

    while(fast&&slow)
    {
        if(fast==slow)
            return fast;

        fast=fast->next;
        slow=slow->next;
    }

    return NULL;
}

image-20220324195236566

第八题：141.环形链表

leetcode：141. 环形链表

image-20220324201734602

本题只需要我们判断该链表是否有环，我们同样使用快慢指针，快指针的速度是慢指针的两倍，进环以后，快指针能追上后来的慢指针，即该链表带环。

带环链表1

如果快指针遇到了NULL，即该链表不带环

题目需要返回bool类型，前面已经提到过了~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool hasCycle(struct ListNode *head) {
    if(head==NULL)
        return false;
    
    struct ListNode * slow=head;
    struct ListNode * fast=head;

    struct ListNode * meet=NULL;
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            return true;
        }
    }
    return false;
    
}

image-20220324214247516

特殊情况：追不上

这里有一个附加的思考问题：fast指针比slow走得快，它们就一定能追上吗？

image-20220324214718688

第九题：142.环形链表Ⅱ（较难😰）

leetcode：142. 环形链表 II

这道题比上一道多了一个要求，需要我们返回链表环形的开始节点

  • 示例1里的开始节点为2（下标为1）
  • 示例2里的开始节点为1（下标为0）

image-20220324202504117

image-20220324202553915

题目分析

这时候，单纯用快慢指针已经不行了，我们还需要想办法找到环的起始节点

8

标出长度，直线部分为L，我们并不知道meet究竟在环的哪一个部分，设环的起点b到meet的长度为X（这里要注意先后顺序，避免搞混，见下图）

9

假设有两个指针，一个head从链表的开头a开始走，一个从meet开始走，最终它们一定会在b点相交！

  • 从meet位置开始走的指针meet，在环里走N*C-X的长度来到b（这里的N指的是在环中走的圈数，是个未知数）
  • 从链表开头a开始走的指针head，走L长度来到b；
  • meet和head每次都走一步（步长相同）；

在上一道链表有环相交的题目中：

  • fast指针走了L+N*C+X的距离；
  • slow指针走了L+X；
  • 慢指针是不可能在环中走超过一圈的，因为快慢指针每次的步长为1，是不可能错过的；
  • fast指针走的距离是slow的两倍，即 L+N*C+X = 2(L+X)；

这时候就能根据上方公式得出一个结论：L = N*C - X；

分解一下这个表达式，L=(N-1)*C + (C-X)，你会发现，C-X不就是meet到b点（相遇点）的距离吗？

以N为1的情况假设，即fast在环内只走了一圈就和slow相遇了，此时公式化简成L = C-X，也就是说，N为1时，一个指针从链表开头开始走，一个指针从相遇位置开始走，它们相交的地方就是链表的环入口。

推广到N大于1的情况，即meet指针走C-X的长度来到b点，再在环内走N-1圈就会与head相遇！不管N是多少，最终都会在环的入口处相遇。

敲代码

分析到这里，我们就可以开始敲代码了~

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
struct ListNode *detectCycle(struct ListNode *head) {
    if (head == NULL)
        return NULL;

    struct ListNode* slow = head;
    struct ListNode* fast = head;

    struct ListNode* meet = NULL;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            meet=fast;//寻找相交点
            break;
        }
    }
    if((fast==NULL)|| (fast->next==NULL))
        return NULL;//如果fast是遇到空退出循环的，说明不带环

    while(1)
    {
        if(head==meet)//相遇点即为环的起点
             return meet;
        
        meet=meet->next;
        head=head->next;
    }

    return NULL;
}

image-20220324203237934

第十题：138.复制带随机指针的链表（很难😱）

LeetCode：138. 复制带随机指针的链表

众所周知，当leetcode给一道题标出“中等”的时候，我这种菜🐕就要写N久，所以对于我来说，简单=有难度，中等=非常难。

本题较难的地方不在于复制链表，而在于处理新链表的random指针

image-20220325091657728

解法一：用计数器找到对应位置

image-20220325091726509

这个方法的缺点是，每一个节点都需要两次遍历，第一次计数，第二次是在新的链表中查找，时间复杂度是O(N^2^)

不过本题并没有对时间复杂度做出要求，所以这个方法肯定也是没问题的！

重点来瞅瞅这个非常女少的解法二

解法二：先复制后断开(๑•̀ㅂ•́)و✧

这个解法的思路是，先在原链表的每一个节点之后插入一个和它相同的新节点

image-20220325093129618

再利用两个指针进行random的查找

  • 第一个7的random是空，我们直接给新的7random置空
  • 第二个13的random指向前一位7，新13的random指向原13random的下一位，即新开辟的7
  • 第三个11的random指向1，新11的random指向原链表1的下一位，即新的1

这样一一对应，就能在新开辟的链表中找到对应的random！

image-20220325093806352

最后，我们需要做的，就是将新开辟的节点从原链表断开，重新链接成新的链表

怎么样，是不是直接一个“妙”就跑出来了？

image-20220325100642282

本题并没有要求不改变原链表，但我们最好还是把原链表还原成初始状态

直接上手敲代码，啪啪啪，一提交，执行出错！

image-20220325100735324

QQ图片20220325100801

仔细找了找，发现是第三个板块最后处理末尾的NULL指针时会出现问题

image-20220325103122093

最后的代码如下！

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
47
struct Node* copyRandomList(struct Node* head) {
	if(head==NULL)
        return NULL;
    //1.复制原链表
    struct Node*HAED=head;//记录头节点
    while(head)//将新链表的每个节点链接在原链表之后
    {
        struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
        newnode->val=head->val;
        newnode->next=head->next;
        head->next=newnode;
        head=head->next->next;
    }
    //2.链接新链表的random
    struct Node* old=HAED;
    while(old)
    {
        struct Node* new=old->next;
        if(old->random==NULL)
            new->random=NULL;
        else
            new->random=old->random->next;

        old=old->next->next;
    }

    //3.将新链表解下来
    struct Node* ret=HAED->next;//记录最后的返回链表
    struct Node* oldlist=HAED;
    while(oldlist)
    {
        struct Node*copy=oldlist->next;
        struct Node*next=copy->next;
        
        oldlist->next=next;

        if(copy->next==NULL)
            copy->next=NULL;
        else
            copy->next=next->next;


        oldlist=next;
    }
 
    return ret;
}

也就执行出错了十几次就找到错误了……问题不大（阿巴阿巴）

image-20220325103204254

第十一题：BM12链表排序

BM12链表排序

给定一个节点数为n的无序单链表，对其按升序排序。

数据范围：0<n≤100000，保证节点权值在[-10^9,10^9]之内。

要求：空间复杂度 O(N)，时间复杂度 O(NlogN)

  • 方法1：因为允许O(N)的时间复杂度，直接将其写入一个数组，排序后重新链接就可以了。std::sort的时间复杂度正好是 O(NlogN)，也符合要求
  • 方法2：采用归并排序，不断左右切分，最小的分支是只有2个节点的时候，排成有序地返回；再将两个链表给连起来

具体的看代码的注释吧！

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <unistd.h>
#include <vector>
class Solution {
  public:
    void PrintList(ListNode* head, const string& pstr) {
        cout << pstr << "  ";
        while (head != nullptr) {
            cout << head->val << " ";
            head = head->next;
        }
        cout << endl;
    }
    // 无差别逆置
    ListNode* reverseNode(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode* ans = reverseNode(head->next);
        head->next->next = head;
        head->next = nullptr;
        return ans;
    }
    // 递归函数
    ListNode* _sortInList(ListNode* head) {
        // 如果只有一个值，直接返回
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        // 如果是两个值，那就进行排序后返回新链表的头
        if (head->next->next == nullptr) {
            ListNode* low = head, *big = head->next;
            if (head->val > head->next->val) {
                low = head->next;
                big = head;
            }
            low->next = big;
            big->next = nullptr;
            return low; // 返回一个升序的链表
        }
        // 如果是超过两个链表，那就进行找中，并将其拆分为两个链表传给自己
        ListNode* slow = head, *fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 走到这里，slow就是中间的值，将其拆分掉
        ListNode* Lhead = head;
        ListNode* Rhead = slow->next;
        slow->next = nullptr;
        // 传递给自己，继续分化
        Lhead = _sortInList(Lhead);
        Rhead = _sortInList(Rhead);
        // PrintList(Lhead, "L");
        // PrintList(Rhead, "R");
        // 最终获取到的两个链表都是有序的，将其连起来
        ListNode phead(0), *cur_next;
        while (Lhead != nullptr && Rhead != nullptr) {
            // 找出小的，头插
            if (Lhead->val < Rhead->val) {
                cur_next = Lhead->next; // 先记录下下一个值
                // 头插
                Lhead->next = phead.next;
                phead.next = Lhead;
                // 移动到原本的下一个值
                Lhead = cur_next;
            } else {
                cur_next = Rhead->next;  // 先记录下下一个值
                Rhead->next = phead.next;// 头插
                phead.next = Rhead;
                Rhead = cur_next;// 移动到原本的下一个值
            }
        }
        // 如果还有剩余值，那就全部头插
        ListNode* not_empty = Lhead != nullptr ? Lhead : Rhead;
        while (not_empty != nullptr) {
            cur_next = not_empty->next;// 先记录下下一个值
            not_empty->next = phead.next;// 头插
            phead.next = not_empty;
            not_empty = cur_next;// 移动到原本的下一个值
        }
        // 因为是把小值头插，最终得到的是降序序列，所以需要逆序
        return reverseNode(phead.next);
    }
    class BigListnode{
    public:
        bool operator()(ListNode*L,ListNode*R){
            return L->val > R->val;
        }
    };
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        // return _sortInList(head); // 方法1，递归+归并
        // 方法2，用vector排序
        ListNode* cur = head;
        vector<ListNode*> nodev;
        while (cur != nullptr) {
            nodev.push_back(cur);
            cur = cur ->next;
        }
        // 排序，写个仿函数（排降序方便头插）
        sort(nodev.begin(),nodev.end(),BigListnode());
        ListNode phead(0);
        // 遍历一遍，重新连起来
        for(auto&e:nodev){
            // 头插
            e->next = phead.next;
            phead.next = e;
        }
        return phead.next;
    }
};

image-20230907122954317

第十二题：876.链表中间节点

https://leetcode.cn/problems/middle-of-the-linked-list/description/

给你一个链表，返回这个链表的中间节点。如果有两个中间节点（链表个数为偶数）则返回第二个中间节点。

这道题用快慢指针就能解决，快指针一次走两步，最终快指针走完的时候，慢指针所在位置就是链表的中间节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head == nullptr){
            return head;
        }
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

第十三题：143.重排链表

https://leetcode.cn/problems/reorder-list/description/

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

1
L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

1
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

这道题的要求是让原本从0到n的链表，变成i到n-i这样依次链接的链表。

最简单的办法是将链表所有节点存入数组，利用数组下标直接用双指针来重新链接链表。但这样会有O(N)的空间复杂度消耗。

正确的思路是利用双指针+链表中间节点+逆置链表+归并链表的思路。这样可以不用额外开空间。面试的时候考察肯定也是希望你写出这样的思路。

  • 先获取链表中间节点，如果是偶数则获取第一个中间节点
  • 逆置右半部分链表（因为获取的是第一个中间节点，右半部分是mid->next）
  • 将左半部分链表置空（mid->next=nullptr)，这也是为什么需要获取第一个中间节点，方便置空，此时原有链表就被拆成了左半部分和右半部分，且右半部分已经被逆置；
  • 依次链接两个链表，从左侧开始，左侧链接右侧，右侧链接左侧的下一个，再依次往后遍历，直到某一个链表为空。

代码如下。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(head == nullptr){
            return;
        }
        // 返回链表中间节点，如果有两个中间节点则返回第1个（方便断开链表）
        ListNode* mid = middleNode(head);
        ListNode* left = head;
        // 逆置右半部分
        ListNode* right = reverseList(mid->next);
        mid->next = nullptr; // 让左半部分和右半部分断开
        // 归并两个链表，从左边开始一次链接一个右侧的链表
        while(left!=nullptr && right!=nullptr)
        {
            ListNode* nextLeft = left->next;
            ListNode* nextRight = right->next;
            // 左边链接右边的
            // 右边的链接左边的下一个
            left->next = right;
            right->next = nextLeft;
            // 注意需要跳转到原本的左侧右侧链表的下一位才可以
            left = nextLeft;
            right = nextRight;
        }
        return;
    }

    // 返回链表中间节点，如果有两个中间节点则返回第1个
    ListNode* middleNode(ListNode* head) {
        if(head == nullptr){
            return head;
        }
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next != nullptr && fast->next->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 逆置链表
    ListNode* reverseList(ListNode* head) {
        // 链表为空时直接返回，链表不为空则到返回最后一个节点
        if(head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* newHead = new ListNode;
        ListNode* cur = head;
        ListNode* prev = newHead;
        while(cur != nullptr)
        {
            ListNode* temp = cur;
            cur = cur->next; // 要在cur的next被修改之前走到下一个节点
            temp->next = prev->next;
            prev->next = temp;
        }        
        return newHead->next;
    }
};

第十四题：25.K个一组翻转链表

https://leetcode.cn/problems/reverse-nodes-in-k-group/

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

这道题包含了链表逆置+快慢指针的思想。

k个一组，很容易想到要用快指针先走k-1步到达需要逆置区间的末尾。

此时有两个问题：逆置后的链表如何链接到原有链表上？逆置了下一个区间如何跟上一个区间连起来？

如下所示

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

当我们逆置了1->2这个链表后，链表应该如下所示

1
2 -> 1 -> 3 -> 4 -> 5

那逆置了3->4后，应该如何将其链接到1节点的末尾呢？

这里也能想到用一个prev指针来记录1节点，但会引出来一个问题，链表开头的1->2链表之前没有prev节点，如何处理呢？

这时候就可以使用头节点了，即new一个新的节点放在原有链表开头

1
H -> 1 -> 2 -> 3 -> 4 -> 5

开始逆置，初始化三个指针如下（下文都是指针，为了方便没有写星号）

1
2
prev = H
slow = fast = 1

首先是让fast指针先走k-1步，此时会走到2节点的位置

1
2
3
prev = H
slow = 1
fast = 2

记录fast节点的下一位为next，即next=3；然后将fast->next设置为nullptr，从slow开始逆置链表，得到逆置后的链表2->1；

经过观察可以发现，逆置后的链表，slow是这个新链表的末尾节点，fast是这个新链表的开头节点。prev暂时没有改动。那么就可以用如下的方式将逆置后的链表插入原有链表

1
2
prev->next = fast;
slow->next = next; // 原本fast的下一个节点

此时链表如下

1
H -> 2 -> 1 -> 3 -> 4 -> 5

随后我们需要更新三个指针，到新的位置处，如下所示

1
2
3
4
prev = slow;
slow = fast = next;
// 即prev在1号节点处
// slow和fast都在3号节点处，准备下一趟循环

重复这个步骤，直到fast走到5时，此时fast->next为空，且需要走的步数还不为0，说明后序的链表已经不足k个，不需要逆置了，跳出循环。

代码如下

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    // 反转链表
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* prv = nullptr;
        ListNode* cur = head;
        while (cur->next != nullptr) {
            // 先记录下下一个节点
            ListNode* next = cur->next;
            // 当前节点链接上一个节点
            cur->next = prv;
            // 更新上一个节点和当前节点
            prv = cur;
            cur = next;
        }
        // cur->next为空了代表走到了原始链表的末尾了
        cur->next = prv;
        return cur;
    }

public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        // 头节点
        ListNode* newHead = new ListNode(0, head);

        ListNode* prev = newHead;
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            int kcount = k - 1; // k = 3时只用走两步
            while (kcount > 0 && fast->next != nullptr) {
                fast = fast->next;
                kcount--;
            }
            // 判断有效性,kcount还有说明末尾的不够用了，不用逆置
            if (fast->next == nullptr && kcount > 0) {
                break;
            }
            // 记录原本的下一位
            ListNode* next = fast->next;
            // 将f的下一个设置为空，让当前链表分离开
            fast->next = nullptr;
            // 逆置slow
            reverseList(slow);
            // 此时fast是新链表的开头，slow是新链表的结尾
            // 将slow的next设置为原本的next，复原到原有链表中
            slow->next = next;
            // 将prev链接为新链表的头
            prev->next = fast;
            // 更新三个指针
            prev = slow;
            slow = next;
            fast = next;
        }
        return newHead->next;
    }
};

image.png

结语💪

刷完这些题，有没有觉得自己对链表的理解直接更上一层楼？

img

如果大家对某道题有问题，或者有我没有说清楚的地方，可以在评论区提出来哦！