【C语言】带你刷爆十道链表OJ
慕雪年华
  2022-03-24 15:23:26 2022-03-24 15:23   2023-04-03 09:23:39    3.7k 字  

[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

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

LeetCode： 876. 链表的中间结点

image

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

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

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

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

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

解法一：遍历

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

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

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

image

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

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

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

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

image

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

  • 先找到这串链表的中间节点（可以用到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

实际上，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

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

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

image

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

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

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

image

这道题也是只有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

第五题：CM11 链表分割

牛客网：CM11 链表分割

image

这道题我使用了带头节点的做法，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

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

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

image

这道题的解析就放注释啦

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

第七题：160.相交链表

leetcode：160. 相交链表

image

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

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

本题思路如下：

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

image

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

第八题：141.环形链表

leetcode：141. 环形链表

image

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

image

如果快指针遇到了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

特殊情况：追不上

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

image

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

leetcode：142. 环形链表 II

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

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

image

image

题目分析

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

image

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

image

假设有两个指针，一个head从链表的开头a开始走，一个从meet开始走

它们一定会在b点相交！

  • 从meet开始走的指针，在环里走N*C-X的长度来到b
  • 从a开始的指针，走L长度来到b

在上一道相交题目中，fast指针走了L+N*C+X的距离，slow指针走了L+X

本题中，meet指针和head指针是同速的，即L=N*C-X

分解一下这个表达式，L=(N-1)*C+(C-X)

你会发现，C-X不就是meet到b的距离吗？

转换为文字说明，即meet指针走C-X的长度来到b点，再走N-1圈与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
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

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

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

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

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

image

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

image

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

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

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

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

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

image

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

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

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

image

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

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

image

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

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

image

image

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

image

最后的代码如下！

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

结语💪

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

image

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

  • 本文标题：【C语言】带你刷爆十道链表OJ
  • 本文作者：慕雪年华
  • 创建时间：2022-03-24 15:23:26
  • 本文链接：posts/3770717253/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
  1. 前言，CSDN的小问题😥
  2. 第一题：206.反转链表
  3. 第二题：876.链表的中间节点
    1. 解法一：遍历
    2. 解法二：快慢指针（很爽👍）
  4. 第三题：OR36 链表的回文结构👨‍🔧
  5. 第四题：链表中倒数第K个节点
  6. 第五题：CM11 链表分割
  7. 第六题：21. 合并两个有序链表
  8. 第七题：160.相交链表
  9. 第八题：141.环形链表
    1. 特殊情况：追不上
  10. 第九题：142.环形链表Ⅱ（较难😰）
    1. 题目分析
    2. 敲代码
  11. 第十题：138.复制带随机指针的链表（很难😱）
    1. 解法一：用计数器找到对应位置
    2. 解法二：先复制后断开(๑•̀ㅂ•́)و✧
  12. 结语💪