【典例】链表经典题目合集

目录导航

这篇目录导航主要目的之一是方便自己以后复习用，都是非常经典的题目。唯一不同的是，下面最后我调试文件贴出来，数据结构很锻炼调试能力，方便大家自己做题出问题时调试，思路没问题情况下，要坚信自己能调出来。每篇文章都包含了，题目链接、思路分析、题解以及sometimes小边独家反思。

小边碎碎念：目前链表极其经典的题目已经更完了，基本上是增删查改的熟练运用，会发现很多题目都是悄悄含着别的题目的影子。比如判断链表是否带环，快慢指针同样是快指针走两步慢指针走一步，其中就含着快慢指针经典题目，寻找返回链表中点，终止条件的判断需要分奇偶数个节点讨论；比如昨天的回文链表，又内含着寻找中间节点，反转单链表这样经典的题目。有一些题目就是分上下集的小故事，有些可以对比一下，有一点小小经验，它们都写在各个文章里了。
这就是经典题目的意义吧，如果不够熟悉，就可能想不到，或者一写就写出小错误，我们不可能背下来它们，但要能做到，拿到之后就能快速正确分析。

正文开始@边通书

1. 删除链表中给定值为val的所有节点

文章链接：小题解

2. 反转一个单链表

文章链接：小题解

3. 返回链表中间节点&返回链表倒数第k个节点

文章链接：小题解

4. 链表的回文结构

文章链接：小题解

5. 合并两个有序链表

文章链接：小题解

6. 输入两个链表，找出它们第一个公共节点

文章链接：小题解

7. 分割链表

文章链接：小题解

8. 判断链表是否带环&找环的入口点

文章链接：小题解

9. 复制复杂链表

文章链接：小题解

10. 调试文件

其实就是自己根据需求手动尾插构建链表，打开监视、内存观察即可。一般错误都能自己调出来。

#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedefint SListDataType;typedefstructSListNode{
    SListDataType data;structSListNode* next;}SLTNode;voidSListPrint(SLTNode* phead){
    SLTNode* cur = phead;while(cur){printf("%d ", cur->data);
        cur = cur->next;}printf("\n");}voidSListDestroy(SLTNode** pphead){// 这个链表是// 链表的空间必须遍历回收，因为申请时候就不连续
    SLTNode* cur =*pphead;
    SLTNode* next = cur->next;// 记录下一个节点的位置while(next){free(cur);
        cur = next;
        next = cur->next;}*pphead =NULL;}//申请新节点
SLTNode*BuyListNode(SListDataType x){
    SLTNode* newnode =(SLTNode*)malloc(sizeof(SLTNode));if(newnode ==NULL){printf("malloc failed\n");exit(-1);}
    newnode->data = x;
    newnode->next =NULL;return newnode;}voidSListPushBack(SLTNode** pphead, SListDataType x){assert(pphead);
    SLTNode* newnode =BuyListNode(x);//1.空链表 - 尾插头结点的地址pList发生改变，因此需要传pList的地址// **ppheadif(*pphead ==NULL){*pphead = newnode;return;}//找尾
    SLTNode* tail =*pphead;while(tail->next !=NULL){
        tail = tail->next;}
    tail->next = newnode;}intmain(){//根据需求尾插构造一个即可return0;}