C语言·链表基础必刷21题 —— 三板斧（上）

C语言·链表基础必刷21题 —— 三板斧（上）

 写在前面

---

• 博客主页：kikoking的江湖背景
• 欢迎关注点赞收藏⭐️留言
• 本文由 kikokingzz 原创，CSDN首发！
• 首发时间：2021年11月30日
• 最新更新时间：2021年11月30日
• ✉️坚持和努力一定能换来诗与远方！
• 作者水平很有限，如果发现错误，请留言轰炸哦！万分感谢感谢感谢！
• 前文简介：
• 第一话·彻底搞清数据结构中的·逻辑结构&存储结构
• 第二话·彻底搞懂数据结构之·算法复杂度
• 第三话·408必看顺序表之·人生不是“顺序表”
• 第四话·数据结构必看之·单链表就这？

---

---

目录

题目1.移除链表元素 

✅思路一：不使用头结点的 *** 作

✅思路二：使用哨兵位的 *** 作

题2.反转链表

✅思路一：直接使用三个指针翻转

✅思路二：头插法

✅思路三：递归法

题3.查找链表中间结点

✅思路：快慢指针

题4.链表中倒数第k个结点

✅思路：早晚指针

题5.合并两个有序链表

✅ 思路一：不带头结点法

✅思路二：带哨兵位

题6.链表分割

✅思路

---

题目1.移除链表元素 

203. 移除链表元素https://leetcode-cn.com/problems/remove-linked-list-elements/description/

✅思路一：不使用头结点的 *** 作

情况1.首元素不为val时

删除的位置是cur，用prev与next相连

    while(cur)
    {
        if(cur->val==val)
        {
            struct ListNode* next=cur->next;
            prev->next=next;
            free(cur);
            cur=next;
        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }

 出现上述报错表示出现了空指针

---

情况2.首元素为val时

if(prev==NULL)//cur是头
{
    free(cur);
    head=next;
    cur=next;
}

---

·完整代码

为什么不使用二级指针？这里的头结点的值不是改变了吗？
使用了一个返回值 struct ListNode* ,因此函数内部改变的头结点的值在函数外也能得到

struct ListNode* removeElements(struct ListNode* head, int val){
//为什么不使用二级指针？这里的头指针的值不是改变了吗？
//使用了一个返回值 struct ListNode* ,因此函数内部改变的头结点的值在函数外也能得到
    struct ListNode* cur = head;
    struct ListNode* prev =NULL ;
    while(cur)
    {
        if(cur->val==val)
        {
            struct ListNode* next=cur->next;
            if(prev==NULL)//cur是头
            {
                free(cur);
                head=next;
                cur=next;
            }
            else
            {
            prev->next=next;
            free(cur);
            cur=next;
            }
        }
    
        else
        {
            prev=cur;//当prev不是NULL时，首元素必然不是val
            cur=cur->next;
        }
    }
    return head;
}

---

✅思路二：使用哨兵位的 *** 作

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* guardHead =(struct ListNode*) malloc(sizeof(struct ListNode));
    guardHead->next=head;//添加一个哨兵位，就不需要考虑头结点为val的情况了
    struct ListNode* prev = guardHead;
    struct ListNode* cur = head;
    while(cur)
    {
        if(cur->val==val)
        {
            struct ListNode* next=cur->next;
            free(cur);
            prev->next=next;
            cur=next;
        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    head=guardHead->next;
    free(guardHead);
    return head;

}

---

题2.反转链表

206. 反转链表https://leetcode-cn.com/problems/reverse-linked-list/description/https://leetcode-cn.com/problems/reverse-linked-list/description/

 ✅思路一：直接使用三个指针翻转

1->2->3->4->NULL
通过3个指针n1n2n3进行翻转
   
  n1  n2 n3
NULL  1->2->3->4->NULL
  
     n1  n2 n3
NULL<-1  2->3->4->NULL
            
        n1  n2 n3 
NULL<-1<-2  3->4->NULL

           n1  n2 n3 
NULL<-1<-2<-3  4->NULL

              n1  n2 n3 
NULL<-1<-2<-3<-4  NULL

struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL||head->next==NULL)//空表，或者只有一个结点的时候
        return head;
    struct ListNode* n1=NULL, *n2=head, *n3=head->next;
    while(n2)
    {
        n2->next=n1;//翻转

        n1=n2;//迭代
        n2=n3;
        if(n3==NULL)//防止空指针的情况
        break;
        n3=n3->next;
    }
    return n1;
}

---

✅思路二：头插法

注意这里头插不创建新结点

cur next
 1 ->2 ->3 ->4->NULL

newHead==NULL

每次取原链表中的结点头插到新结点
需要两个指针，一个用来头插，一个用来标识下一个结点

cur->newHead
 1->NULL
cur=newhead

-----step2-----

   cur next
 1->2 ->3->4->NULL

 cur->newHead->NULL
   2->1->NULL
cur=newHead

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* cur=head , *newHead=NULL;
    while(cur)
    {
        struct ListNode* next=cur->next;
        cur->next=newHead;
        newHead=cur;
        cur=next;
    }
    return newHead;
}

---

✅思路三：递归法

把大问题变成小问题，拆分求解

---

题3.查找链表中间结点

876. 链表的中间结点https://leetcode-cn.com/problems/middle-of-the-linked-list/description/https://leetcode-cn.com/problems/middle-of-the-linked-list/description/

 ✅思路：快慢指针

慢指针走一步，快指针走两步；等到快指针走完了，慢指针刚好走了一半

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode *fast = head, *slow = head;
    while(fast&&fast->next)
    {
        slow=slow->next;//slow走一步
        fast=fast->next->next;//fast走两步
    }
    return slow;
}

---

题4.链表中倒数第k个结点

链表中倒数第k个结点https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-rankinghttps://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

✅思路：早晚指针

---

struct ListNode* FindKthToTail(struct ListNode* pListHead,int k) 
{
    struct ListNode* early=pListHead, *late=pListHead;
    while(k--)//这里是k--走k次  --k走（k-1）次
    {
        late=late->next;
    }
    while(late)
    {
        early=early->next;
        late=late->next;
    }
    return early;
}

出现如下问题：

自己测试数据，或者在VS上可以跑过，但是在牛客，leetcode上跑不过是为啥呢？

自己测试可以跑过，但是系统跑不行，这时思考：

1. 自测常规情况，可以过
2. 打印一些标记值，不显示输出标记值。比如：段错误
3. 思路极端情况场景测试用例

考虑极端情况：
1.k的值比链表长度长------->会发生什么------->会产生空指针！

struct ListNode* FindKthToTail(struct ListNode* pListHead,int k) {
    struct ListNode* early=pListHead, *late=pListHead;
    while(k--)//这里是k--走k次  --k走（k-1）次
    {
        if(late==NULL)
        {
            return NULL;
        }
        late=late->next;
    }
    while(late)
    {
        early=early->next;
        late=late->next;
    }
    return early;
}

成功！

---

leetcode环境很舒服，因为错了会报测试用例，针对测试用例去分析

牛客等环境，不一定会报测试用例，大家还得学会排除法+极端场景猜测法

校招笔试大多都是 牛客+赛马

---

题5.合并两个有序链表

21. 合并两个有序链表https://leetcode-cn.com/problems/merge-two-sorted-lists/

✅ 思路一：不带头结点法

---

把小的值进行尾插

 

struct ListNode* mergeTwoLists(struct ListNode* n1, struct ListNode* n2){

//提前判断空链表的情况
if(n1==NULL)
    return n2;
if(n2==NULL)
    return n1;

struct ListNode*head=NULL, *tail=NULL;
//先取一个小的做第一个结点，方便后面尾插

if(n1->valval)
{
    head=tail=n1;
    n1=n1->next;
}
else
{
    head=tail=n2;
    n2=n2->next;  
}

while(n1&&n2)
{
    if(n1->valval)
    {
        //取小的尾插到新链表
        tail->next=n1;
        n1=n1->next;
    }
    else
    {
        tail->next=n2;
        n2=n2->next;
    }
    tail=tail->next;
}
if(n1==NULL)
{
    tail->next=n2;
}
else
{
    tail->next=n1;
}
return head;

}

成功！

✅思路二：带哨兵位

---

struct ListNode* mergeTwoLists(struct ListNode* n1, struct ListNode* n2){
struct ListNode*head=NULL, *tail=NULL;

head = tail =(struct ListNode*)malloc(sizeof(struct ListNode));

tail->next=NULL;

while(n1&&n2)
{
    if(n1->valval)
    {
        //取小的尾插到新链表
        tail->next=n1;
        n1=n1->next;
    }
    else
    {
        tail->next=n2;
        n2=n2->next;
    }
    tail=tail->next;
}
if(n1==NULL)
{
    tail->next=n2;
}
else
{
    tail->next=n1;
}
struct ListNode* cur=head->next;
free(head);
head=NULL;
return cur;

}

---

题6.链表分割

CM11 链表分割https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-rankinghttps://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

✅思路

1.把小于x尾插到一个链表（带哨兵位，方便尾插，不用考虑空指针）

2.把大于x尾插到一个链表（带哨兵位，方便尾插，不用考虑空指针）

3.最后再把两个链表链接在一起

class Partition {
public:
   struct ListNode* partition(ListNode* pHead, int x) {
       ListNode* lessHead, *lessTail, *betterHead, *betterTail;
       lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
       betterHead=betterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
       lessTail->next=NULL;
       betterTail->next=NULL;
       
       struct ListNode* cur=pHead;
       while(cur)
       {
           if(cur->valnext=cur;
               lessTail=lessTail->next;
           }
           else
           {
               betterTail->next=cur;
               betterTail=betterTail->next;
           }
           cur=cur->next;
       }
       //链接两个链表
       lessTail->next=betterHead->next;
       (？？？？？？？？？？？？？？？？？？？）
       pHead=lessHead->next;
       free(lessHead);
       free(betterHead);
       return pHead;
    }
};

内存超限：隐藏的bug导致的

通过VS自测可以过，特殊场景过不去

可 *** 作的测试用例：（大家可以复制下面的main函数，然后将自己写的接口函数也拷贝进VS中，方便运行）

int main()
{
    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));

    n1->val = 2;
    n2->val = 4;
    n3->val = 9;
    n4->val = 3;
    n5->val = 2;
    n6->val = 1;
    n7->val = 6;

    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n5;
    n5->next = n6;
    n6->next = n7;
    n7->next = NULL;

    struct ListNode* head = Partition().partition(NULL, 5);

    PrintList(head);

    return 0;


}

 分析模式开始：可能哪里出现了问题？

思路：这种题一般都要考虑一个头和尾

 

可知上述代码的（？？？？？？？？？？？？？？？？？？？）中应当填写下面代码

将betterTail的next置为NULL，这样就会避免带环链表的问题

betterTail->next=NULL: