【数据结构】励志大厂版·初阶（复习+刷题）单链表

前引：此篇文章作为小编复习的记录，将快速回忆单链表的知识点，讲解单链表增删查找的实现，每个细节之处要注意的地方，解释为何这样设计。文章末尾包含了单链表算法题， 同样解释详细，借助题目再次巩固知识点，挑战实战应用，喜欢的伙伴们可以作为大家的复习资料，希望可以给个免费的一键三连哦！正文开始~

目录

知识点速览

单链表实现

定义结构体

初始化

开辟节点

尾插 

头插

尾删

头删

 在指定位置之前插入

在指定位置之后插入

链表 OJ（1）

链表OJ（2）

链表OJ（3）

链表OJ（4）

链表OJ（5）

---

知识点速览

链表较顺序表而言的优点是地址不连续、空间利用率很高，同样属于线性结构，它的空间是一个个结构体，既可以存储数据，也通过指针存储下一个结构体的地址，实现链式结构，如下抽象理解：

单向不带头非循环链表是最简单的一种链表结构，单链表的实现，需要一个头指针指向第一个节点，然后再后面一个接一个的开辟其它节点，这里下面实现的时候再详细说，下面看看经常说的几个链表名词是哈意思：

单链表结束标志：最后一个节点的指针的 next 指向空（NULL）

头指针：一个结构体类型的指针，用来指向链表的第一个节点

头节点：在第一个节点之前再连接一个节点，通常可以称为哨兵节点，如下图：

带头节点：头指针指向头节点

不带头节点：头指针指向第一个节点

逻辑结构：比如这里我们将链表想象成了一节一节的样子，通过指针连接，在实际操作中方便理解

物理结构：比较严谨，链表的物理结构是下面这样的，上一个节点存放下一个节点的地址

拓展：指针指向的是地址，是数据具有多个字节的第一个字节的地址（每个字节都有一个地址）

单链表实现

定义结构体

每个链表的节点空间其实是一个结构体，下面我们构建链表节点空间，这个结构体里面有一个指针（用来指向下一个节点的地址），一个数据域（用来存储数据）

typedef int Plastic;typedef struct List
{//结构体指针struct List* next;//数据域Plastic data;
}List;

初始化

我们知道链表有一个头指针（结构体类型），用来指向链表的第一个节点，开始还没有开辟节点，所以它的指向应该是空（NULL）

List* pphead = NULL;

 在整个链表中，我们都需要注意以下几点，小编都帮大家整理出来了！希望可以支持一下小编哦

（1）如果需要改变头指针的位置，就传指针地址，采用二级指针接收

          如果不需要改变头指针的位置，就传指针，采用一级指针接收

          例如：我们头插的时候，需要让头指针指向第一个节点，就需要改变头指针位置

（2）链表不存在：我们判断一个链表存不存在，是看它的头指针存不存在

         链表为空：链表为空不代表链表不存在，只是里面没有插入节点，只有一个头指针指NULL 

         例如：二级指针，pphead==NULL，就表示这个链表不存在；*pphead==NULL，为空链表

开辟节点

这里为了后面方便，考虑到需要多次开辟节点，我们将它单独设置在一个函数，开辟之后根据常规流程，需要判断空间的有效性，其次是需要初始化空间，如下：

//开辟节点
List* Newnode(int data)
{//开辟新节点List* newnode = (List*)malloc(sizeof(List));if (newnode == NULL){printf("开辟失败\n");return NULL;}//初始化节点内容newnode->next = NULL;newnode->data = data;return newnode;
}

尾插 

尾插的步骤是先找尾，再插入。如何找尾？新定义一个指针从链表头部开始一个个遍历，直到它的下一个是空，然后将新开辟的节点连接在这个指针的后面，例如我现在定义了一个指针 cur ：

为什么判断条件是“  cur->next  ！= NULL ”？

假设，如果cur！=NULL，那么此时cur已经走到了链表的末尾，也就是“NULL”处，如果接下来要插入新节点，那么表示“NULL->next ==新节点”，这样很明显是错误的方式。下面看尾插结果：

//尾插
void Tail_insert(List** pphead,int data)
{//看链表存不存在assert(pphead);//如果是空链表if (*pphead == NULL){*pphead = Newnode(data);return;}//设置新指针，指向链表开头List* cur = *pphead;//找尾while ((cur->next) != NULL){cur = cur->next;}//找到之后进行插入cur->next = Newnode(data);
}

头插

头插我们不需要去找头，因为头指针所指的节点就是该链表的第一个节点，那么如何头插？如下图

先设置一个指针，让其下一个节点是 pphead 指向原先的第一个节点，然后再更新 pphead 指向

//头插
void Head_insert(List** pphead,int data)
{//判断链表是否存在assert(pphead);//如果是空链表if (*pphead == NULL){*pphead = Newnode(data);return;}//开辟节点List* cur = Newnode(data);//设置前后关系cur->next = *pphead;//更新头指针指向*pphead = cur;
}

尾删

尾删肯定需要先遍历找尾，找尾的条件应该是“cur->next ！= NULL”

其次还需要找到 cur 的前面一个节点，因为尾删之后，我们需要释放尾部节点，然后尾部前面的节点关系应该是prev->next==NULL。如果未重新确立next的关系，链表就出问题了，如下图理解：

//尾删
void Tail_deletion(List* pphead)
{//判断空链表assert(pphead);List* cur = pphead;List* prev = pphead;//找尾while (cur->next != NULL){prev = cur;cur = cur->next;}//释放free(cur);cur = NULL;//改变尾部关系prev->next = NULL;
}

头删

头删需要先找到当前头指针指向节点的下一个节点，然后对头指针所指向的节点释放，再更新头指针（如果先更新再释放，那么我们就找不到原来的第一个节点了，切记！）

 头删之前

                                                                        头删之后  

//头删
void Head_deletion(List** pphead)
{//判断链表释放存在assert(pphead);//判断空链表assert(*pphead);//如果只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}//先找到第二个节点List* cur = (*pphead)->next;//释放头指针所指向的节点free(*pphead);//更新头指针指向*pphead = cur;
}

 在指定位置之前插入

我们先来看图

这里同尾删一样，需要两个指针，一个找指定位置，一个找指定位置的前一个位置，再来确立next的关系即可。这里不需要去改变头指针的位置，所以使用一级指针就可以！

下面我们来看看插入前与插入后的效果

//在指定位置前插入
void Before_position(List** pphead, int data)
{//判断链表是否存在if (pphead == NULL){return;}//如果是头插if (data == (*pphead)->data){Head_insert(pphead, 5);return;}List* cur = pphead;List* prev = pphead;//找指定位置while (cur->data != data){prev = cur;cur = cur->next;}//插入节点、设置关系prev->next = Newnode(5);prev->next->next = cur;
}

在指定位置之后插入

在指定位置后面插入还是需要另外定义两个指针，先标记cur->next的节点，插入之后方便连接

 插入前插入后的效果展示

//在指定位置后插入
void Behind_position(List* pphead, int data)
{//判断空链表if (pphead == NULL){return;}List* cur = pphead;List* pc = cur->next;//找指定位置while (cur->data != data){cur = cur->next;}//插入cur->next = Newnode(6);//连接（确认next的关系）cur->next->next = pc;
}

链表 OJ（1）

首先跟随小编来分析一下这个题目：此题是将一个无头单向不循环链表进行翻转，原来的首尾全部倒置过来，需要考虑到链表为空、是否越界的情况，以上就是简单的分析，下面进行思路讲解

思路讲解：

（1）反转链表，我们实际上是反转它的箭头指向。这题我们肯定要记录它的下一个节点。因此避免越界，我们应该先进行判断，防止空链表 和 一个节点的情况

（2）排除以上两种特殊情况之后。我们先设置三个变量（下面小编会分析原因！）

分别是 cur ，刚开始指向空；next 指向 head ->next；pc 指向 head。具体指向如图：

 我们通过三个指针的走动来改变链表的指向，例如：

（3）第一轮循环

pc->next = cur;cur = pc ;
pc = next ;
next = next->next;

在开始时，我们的指针是上面这样的。此时改变pc的指向，pc->next=cur，这时第一个节点就已经翻转过来了，如图：

然后改变三个指针的指向     cur=pc  pc=next  next=next->next     第一轮循环就走完了

（4）第二轮循环

执行第一条语句  pc->next=cur  ，就翻转了第二个节点

然后执行  cur=pc  pc=next  next=next->next  就改变了三个指针的指向，如下图：

（5）就这样经过几轮循环

while (next != NULL)
{pc->next = cur;cur = pc ;pc = next ;next = next->next;
}

next已经指向空，循环停止，前面的链表节点已经完全翻转过来了，如下图：

再将剩余的一个节点 翻转过来 pc->next=cur 此时整个链表就翻转过来了

链表OJ（2）

分析题目：这题是找到链表的中间节点，因此最简单的方式就是通过遍历链表，记录链表的长度，最后通过除法确立链表的中间节点，再次遍历返回节点 （此题并不难，暴力解法也是算法哦！）

思维讲解：

我们可以先来遍历链表，记录链表的长度。需要注意空链表的情况

//如果链表为空
if (head == NULL)
{return NULL;
}//遍历链表、记录长度
int count = 0;
struct ListNode* cur = head;while (cur != NULL)
{count++;cur = cur->next;
}

然后通过节点计算中间节点

//计算中间节点
count = count / 2 + 1;

再次遍历节点，通过  count  的减减来返回节点

//再次找中间节点，并返回
cur = head;
while (cur != NULL)
{count--;if (count == 0){break;}cur = cur->next;
}
return cur;

链表OJ（3）

 题目分析：

（1）此题是合并两个有序的链表，方法与“合并两个数组”有异曲同工之妙，但是这里不用创建新的链表，因为题目已经形成了两个链表，我们只需要创建一个头指针改变链表节点的指向就行了

例如：将 List2 剩余的节点移给 pphead ，并不用去创建新的链表

（2）初始化时我们设置2个指针 分别是  pphead  cur，用来组成新的链表，开始时二者都为空

（3）如果存在某个链表是空，或者都为空。那么就直接返回，这是两种特殊情况

 if(list1==NULL){return list2;}if(list2==NULL){return list1;}

 （4）现在我们通过找两个链表的较小值，来选取节点进行重新组合。因为开始pphead  cur 是空，所以需要先处理这种情况，第一次循环找到的较小值应该更新pphead cur，例如：

 if(pphead==NULL){pphead = list1;cur=pphead;}

（5）随后根据找较小值，进行组合就行了，记得更新对应的指针。直到二者有一个为空就结束

 while(list1 != NULL && list2 != NULL){//如果list1的当前节点小if(list1->val <= list2->val){if(pphead==NULL){pphead = list1;cur=pphead;}else{cur->next=list1;cur=cur->next;}list1=list1->next;}//如果list2的当前节点小else{if(pphead==NULL){pphead=list2;cur=pphead;}else{cur->next=list2;cur=cur->next;}list2=list2->next;}}

（6）此时可能有某个链表的节点未排完且链表是有序的，根据判断语句，连接到  cur  指针的后面

 //对剩余的链表元素进行连接if(list1 == NULL){cur->next=list2;}if(list2==NULL){cur->next=list1;}

链表OJ（4）

题目分析：

此题是通过判断这个链表是否有循环部分来返回不同的值，我们不能通过遍历去做这题，不然效率特别低，甚至做不出来，这里小编直接告诉大家一种算法：双指针（快慢指针），咱们先按照这个思路来直接解题，先不考虑如何优化！但是此题真正需要了解的是后面的证明，因为很多面试题是问如何证明二者是否相遇（证明在最后哦！）小编先来讲如何实现，再来解决推理证明问题！

思维分析：

快慢指针是通过两个指针的移动速度不同，来判断二者是否相遇返回不同的值

例如：现在有两个指针cur和prev，prev的速度是cur的两倍。如果链表有环，那么当prev进入环内，cur也会因为与prev的速度不同被prev追赶，二者终会相遇，此时链表有环；如果链表没有环，那么prev就会走到空（NULL），得出链表没有环。下面是图示，已助理解！

（1）如果链表为空，直接返回false ；

         否则设置两个结构体指针 prev 与 cur ，prev的移动速度是cur的两倍

（2）循环的条件应该是prev不为空，否则直接返回false。那么如何实现快慢呢？

         最简单的方法就是通过次数，比如prev动一次就记录一次，动了两次就轮到cur走一次，然             后重新记录次数。大家可以看下面的代码来理解，小编已经全部注释了！

int count=0;
while(prev){//如果prev动了两次，就轮到cur走了if(count==2){cur=cur->next;//如果cur动的时候遇到了prev，就直接返回trueif(cur==prev){return true;}//重新记录prev动的次数count=0;}else{//prev动一次，就记录一次count++;prev=prev->next;//如果prev遇到了cur，直接返回trueif(prev==cur){return true;}}}
return false;

代码优化：

直接控制指针的next来实现走动次数，减少了冗杂的条件判断（下面主要是优化了循环部分）

bool hasCycle(struct ListNode *head) 
{//如果链表为空if(head==NULL){return false;}//设置两个链表指针struct ListNode* prev=head;struct ListNode* cur=head;while(prev && prev->next)      //     优化{//cur每次走一步，prev每次走两步cur=cur->next;prev=prev->next->next;//如果相遇if(prev==cur){return true;}}return false;
}

证明推理：

问：既然一个走一步，一个走两步可以相遇；那么一个走一步，一个走三步呢？以此类推，请证明

首先一个走一步，一个走二步，即二者只差一个单位是一定可以追上的，推理如下：

假如当 cur 进入循环，prev 此时也在循环内，二者相差 N ，如图：

此时 prev 走两步，cur 走一步，二者相差 N-1 ；prev 再走两步， cur 再走一步，二者相差 N-2，那么推下去，N一定会等于 0，也就是二者一定相遇 

如果一个走一步，一个走三步呢？是可能永远追不上的，推理如下：

还是当 cur 进入循环，prev 与 cur 相差 N

此时 prev 走三步，cur 走一步，二者相差 N-2 ；prev 再走三步，cur再走一步，相差 N-4；继续推下去，如果 N 是偶数，那么会相遇距离为 0 ；如果 N 是奇数，二者最终会是 -1 ，即 prev  超过了cur ，为下面这个场景：

此时 二者相距 C-1（C为圆周长）。prev 再走三步，cur 再走一步，二者相距 3，推理下去，当二者相距 N ，随着二者之间永远相差 2 个单位，就一直无法相遇。其它情况同理类推即可 

链表OJ（5）

题目分析：

此题是找到环形链表入环的第一个节点，此题同上题一样，在很多面试题中重点要求证明推理，因此小编会先讲如何证明，当我们知道这个推理过程之后，写起来会很轻松，否则实现真的很难！

证明推理：

我们假设进入 环 之前的距离为 L ，它们在环的  end  位置相遇，其它变量如图所示：

cur 从起点走到相遇位置用的距离：L +  X

prev 从起点到相遇位置用的距离： L + X + C

但是 prev 走的比 cur 快，不可能在第一圈内就与 cur 相遇，肯定是在第一圈之后才追赶到的 cur ，具体的圈数我们是无法确定的，因为这个环可大可小，比如：

所以 prev 正确走的距离应该是 ： L + X + N * C （N为未知数，表示几倍的关系）

那么 cur 与 prev 走的路程关系为 ：2（ L+X）= L + X + N * C（因为prev的速度是cur的两倍）

所以我们得到  ：L + X = N * C

                         L + X = （ N - 1 ）* C + C

最终我们将整倍的圆周路程不看，可以得到：L +  X  =  C

                                                         也就是： C - X  =  L    （即下面两段红线长度相等）

那么入环点不就是从   相遇位置  与从  起点    开始运动相遇的位置吗？因此我们来实现代码：

（1）先找prev 与 cur二者相遇的位置 （2）设置一个指针pc指向head ，返回cur与pc相遇点

 

struct ListNode *detectCycle(struct ListNode *head) 
{//判断空链表if(head==NULL){return NULL;}//设置双指针找相遇位置struct ListNode* prev=head;struct ListNode*cur=head;struct ListNode* pc=head;while(prev && prev->next){//prev每次走两步prev=prev->next->next;//cur每次走一步cur=cur->next;//找相遇位置if(cur==prev){//pc指针从开头开始走，cur指针从相遇位置开始走，二者相遇既是环的起点while(pc != cur){cur=cur->next;pc=pc->next;}//此时二者相遇,返回环的起始位置return cur;}}return NULL;
}

好了伙伴们，链表OJ题就到这里结束了！大家千万要弄懂最后两题的证明推理啊！可以关注收藏起来！希望大家面试的时候刚好遇到了今天小编整理的最后两题 ，直接写答案！