目录
??一、题目解析
1.1删除链表中等于给定值 val 的所有节点（力扣）
1.2反转一个单链表。（力扣）
1.3给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个 中间结点。（力扣）
1.4输出链表中倒数第k个结点。
1.5将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
1.6编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
1.7 链表的回文结构
1.8输入两个链表，找出它们的第一个公共结点。
1.9给定一个链表，判断链表中是否有环。
1.10给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
??一、题目解析

1.删除链表中等于给定值 val 的所有节点。 2.反转一个单链表。 3.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个 中间结点。 4.输出链表中倒数第k个结点。 5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 6.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。 7.链表的回文结构。 8.输入两个链表，找出它们的第一个公共结点。 9.给定一个链表，判断链表中是否有环。 10.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

1.1删除链表中等于给定值 val 的所有节点（力扣）
文章图片

?思路一：剔除某些值，反之，保留某些值。
将不等于val的节点全都尾插至新的链表中，然后返回新的头节点。
细节：
新的链表尾指针需指向空
否则遇到1->2->3->6->5->8->6val=6。这种情况会有问题。
因为tail的最后的指向是8，而8指向6，6指向空。
最后的错误输出是1->2->3->5->8->6。
解决：在cur退出循环的时候，将tail->next=NULL。但要保证前题tail不为空。

代码：

typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* newhead=NULL; struct ListNode* newtail=NULL; struct ListNode* cur=head; while(cur) { if(cur->val!=val) { //将节点尾插至新链表 if(newhead==NULL) { newhead=newtail=cur; } else { newtail->next=cur; newtail=cur; } } cur=cur->next; if(cur==NULL) { if(newtail) newtail->next=NULL; } } return newhead; }

?思路二：在原链表中操作，找到等于val值的节点，在删除它，这种删除就是把它前一个指针的指向后一个节点的地址。 图解：
文章图片
细节：
当要删除的节点为头节点时，prev==NULL。
struct ListNode* temp=cur;
cur=cur->next;
prev->next=cur; （对空指针解引用，发生错误）。
free(temp);
解决：
【数据结构|《数据结构》十道链表经典面试题多种方法深度解析】分情况讨论，当要删除的节点是头节点时。执行以下操作。
cur=cur->next;
free(newhead);
newhead=cur;

代码：

typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head, int val) { if(head==NULL) { return head; } struct ListNode* prev=NULL; struct ListNode* newhead=head; struct ListNode* cur=head; while(cur) { if(cur->val==val) { if(cur==newhead) { cur=cur->next; free(newhead); newhead=cur; } else { struct ListNode* temp=cur; cur=cur->next; prev->next=cur; free(temp); } } else { prev=cur; cur=cur->next; } } return newhead; }

1.2反转一个单链表。（力扣）
文章图片

?思路一：
三指针法：前指针 中指针 后指针
翻转部分：中指针指向前指针
迭代部分：前指针=中指针；中指针=后指针；后指针=后指针->next。
图解：

文章图片

细节：
最后循环的结束条件是n2==NULL。当n2是最后一个节点的地址时，n3是为空的。迭代部分将n3赋值给n2，此时再进行n3=n3->next显然是不合适的。
解决：

if(n3) n3=n3->next;

代码：

struct ListNode* reverseList(struct ListNode* head) { if(head==NULL) { return head; } struct ListNode* n1=NULL; struct ListNode* n2=head; struct ListNode* n3=head->next; while(n2) { //翻转部分 n2->next=n1; //迭代部分 n1=n2; n2=n3; if(n3) n3=n3->next; } return n1; }

?思路二：
头插法：将原链表的节点头插至新链表，新链表初始为空。
图解：

文章图片

代码：

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

1.3给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个 中间结点。（力扣）

?思路一：
快慢指针：一个快指针（fast），一个慢指针(slow)。初始状态它们都指向空，快指针一次走两步，慢指针一次走一步。当节点数为偶数时，快指针走到NULL时，slow就是中间节点，当节点数为奇数时，快指针走到最后一个节点时，slow就是中间节点。
图解：

文章图片

文章图片

代码：

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

?思路二：
求总链表长度，取一个cur指针，它初始指向head，走总链表长度/2的步数即到达中间节点。

1.4输出链表中倒数第k个结点。
文章图片

?思路一：
快慢指针：一个快指针（fast），一个慢指针（slow），起初它们都指向head。先让fast走k步，此时它们之间的距离就是k，在同时让快指针走一步，慢指针走一步，当快指针走到NULL时，slow即为倒数第k个节点。
细节：
当输入的k大于节点个数时，会出现fast越界的问题。
解决：
在fast移动之前判断fast是否为空，如果为空则返回NULL，不为空就向后移动。

代码：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { if(pListHead==NULL) { return NULL; } struct ListNode* prev=pListHead; struct ListNode* cur=pListHead; while(k--) { if(cur) cur=cur->next; else { return NULL; } } while(cur) { cur=cur->next; prev=prev->next; } return prev; }

1.5将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
文章图片

?思路一：
归并思想：取一个初始为空的新链表，比较指向list1和指向list2的节点值，小的先放入新链表，放完之后，小的节点指针向后移动。当有一个指针为空时，就将另一个链表直接连接至新链表。

代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } struct ListNode* cur1=list1; struct ListNode* cur2=list2; struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* tail=newhead; while(cur1 && cur2) { if(cur1->val>cur2->val) { tail->next=cur2; tail=cur2; cur2=cur2->next; } else { tail->next=cur1; tail=cur1; cur1=cur1->next; } } if(cur1) { tail->next=cur1; } else { tail->next=cur2; } return newhead->next; }

1.6编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。

?思路一：
取新链表less和新链表greater，它们初始都为空。然后用指针cur遍历一遍原链表，小于x的节点放入less链表中，大于x的放入greater链表中，最后再将less和greater连接起来，返回less的头指针。
细节：
小于x的节点放less链表中，不要写成小于等于x的节点放入less链表中。
当less为空时，返回greater的头指针。
当less不为空时，less最后的节点要指向greater的头节点。并且将greater最后节点的指针指向空。因为greater最后的指向可能指向less的某个节点，连接less和greater的时候就会形成环。
图解：

文章图片

代码：

class Partition { public: ListNode* partition(ListNode* pHead, int x) { ListNode* less=NULL; ListNode* lesstail=NULL; ListNode* greater=NULL; ListNode* greatertail=NULL; ListNode* cur=pHead; while(cur) { if(cur->valnext=cur; lesstail=cur; } } else { if(greater==NULL) { greater=greatertail=cur; } else { greatertail->next=cur; greatertail=cur; } } cur=cur->next; } if(less) { lesstail->next=greater; if(greatertail) { greatertail->next=NULL; } return less; } else { return greater; } } };

1.7 链表的回文结构

什么是回文结构？就是正着读和反着读没区别，即对称的图形。
比如1->2->3->2->1。该结构就是回文结构。
?思路一：
找中间节点，然后翻转中间节点至最后节点组成的链表
图解：

文章图片


文章图片

如果head1链表和head2链表一致则说明该链表是回文结构。
结束条件是：head2==NULL。
偶数个节点情况：

文章图片

与奇数个链表的情况结束条件一致。

代码：

class PalindromeList { public: bool chkPalindrome(ListNode* A) { //找中间节点 ListNode* slow=A; ListNode* fast=A; ListNode* mid=NULL; ListNode* head1=A; ListNode* head2=NULL; while(fast && fast->next) { slow=slow->next; fast=fast->next->next; } mid = slow; //逆置mid-NULL各节点(核心) ListNode* n1=NULL; ListNode* n2=mid; ListNode* n3=mid->next; while(n2) { n2->next=n1; n1=n2; n2=n3; if(n3) n3=n3->next; } head2=n1; //判断是否回文 while(head2) { if(head1->val != head2->val) { return false; } head1=head1->next; head2=head2->next; } return true; } };

1.8输入两个链表，找出它们的第一个公共结点。
文章图片

?思路一：
先判断是否存在交点，判断方法如下：
当A和B有相同的尾节点，则说明A和B有交点。
当存在交点时，让长的链表（图B）先走A和B链表长度的差距步，然后让A和B同时走，直到指针A等于指针B，此时指针A就是交点的地址。
图解：
先让headB走差距步，即走1步。

文章图片

让headA和heaB同时走，直到headA等于headB，此时headA就是交点的地址。

文章图片

代码：

typedefstruct ListNode ListNode; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { ListNode* list1_tail=headA; ListNode* list2_tail=headB; ListNode* greater=headA; ListNode* less=headB; int lenA=1; int lenB=1; //判断是否有交点的核心思想:尾部节点的地址一致。 while(list1_tail->next) { list1_tail=list1_tail->next; lenA++; } while(list2_tail->next) { list2_tail=list2_tail->next; lenB++; } if(list1_tail!=list2_tail) { return NULL; } //找交点 int gap=abs(lenA-lenB); if(lenAnext; } while(greater && less) { if(greater == less) { return less; } greater=greater->next; less=less->next; } return NULL; }

1.9给定一个链表，判断链表中是否有环。
文章图片

?思路一：
快慢指针：定义两个指针，一个快指针（fast）,一个慢指针（slow），初始它们都指向头节点，快指针一次走两步，慢指针一次走一步，如果有环，则快指针必定与慢指针在环的某个节点处相遇。无环，则它们绝对不会相遇。
细节：

while(fast && fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) { return true; } }

能这样写吗？
不能，因为初始值slow和fast是相等的，直接就return true了。
正确写法：

while(fast && fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) { return true; } }

讨论：
如果fast一次走两步，slow一次走一步，它们一次会相遇吗？
如果fast一次走3步，slow一次走1步，它们一次会相遇吗？
如果fast一次走4步，slow一次走一步，它们一次会相遇吗？

代妈：

typedef struct ListNode ListNode; bool hasCycle(struct ListNode *head) { ListNode* slow=head; ListNode* fast=head; while(fast && fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) { return true; } } return false; }

1.10给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
文章图片

?思路一：
先判断是否有环，使用快慢指针的方法。
如果有环，则记录快指针和慢指针相遇的节点地址。

文章图片

假设在值为4的位置快慢指针相遇，我们让mee指向相遇点。
此时我们做如下操作：
newhead=meet->next（让newhead指向值为5的这一节点）。
然后mee->next=NULL。（让meet指向空）。
此时图转化为：

文章图片

我们调整一下图

文章图片

我们要找的环入口就是head和newhead两链表的相交点。
与题1.8解法一致。

代码：

typedef struct ListNode ListNode; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { ListNode* list1_tail=headA; ListNode* list2_tail=headB; ListNode* greater=headA; ListNode* less=headB; int lenA=1; int lenB=1; //判断是否有交点的核心思想:尾部节点的地址一致。 while(list1_tail->next) { list1_tail=list1_tail->next; lenA++; } while(list2_tail->next) { list2_tail=list2_tail->next; lenB++; } if(list1_tail!=list2_tail) { return NULL; } //找交点 int gap=abs(lenA-lenB); if(lenAnext; } while(greater && less) { if(greater == less) { return less; } greater=greater->next; less=less->next; } return NULL; } struct ListNode *detectCycle(struct ListNode *head) { ListNode* slow=head; ListNode* fast=head; ListNode* meet=NULL; ListNode* head1=head; while(fast && fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) { meet=fast; //找交点，即链表head1和链表head2的公共节点。 ListNode* head2=meet->next; meet->next=NULL; return getIntersectionNode(head1,head2); } } return NULL; }

?思路二：
数学推理法：与思路一相同，先用快慢指针判断是否出现环，如果无环，直接返回NULL，如果有环，则记录快慢指针的相遇点。

文章图片

设从头节点到环的入口点的步数为L，环的长度为C。
假设环入口点走x步快慢指针相遇了。
可得出：
慢指针走的路程为：L+X。
快指针走的路程为：L+X+C*N（其中N代表圈数，N>=1）。
快指针路程是慢指针路程的两倍
所以：L+X+C*N=2*(L+X)。
化简得：L=C*N-X
L=C*(N-1)+C-X。
因此我们只需要让一个指针从head走，另一个指针从meet走，当两指针相等时，它们就指向环的入口点。

代码：

typedef struct ListNode ListNode; struct ListNode *detectCycle(struct ListNode *head) { ListNode* slow=head; ListNode* fast=head; ListNode* cross_point=NULL; while(fast && fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) { cross_point=slow; while(cross_point!=head) { head=head->next; cross_point=cross_point->next; } return cross_point; } } return NULL; }

推荐阅读

• 

  外国ios账号，求分享一个美国的apple id谢谢了
• 

  汽车转速表一直在1降不到0还能开吗
• 

  唐山牛年纪念币预约 2023年唐山贺岁纪念币在哪里预约
• 

  云原生应用之旅——Kubernetes成长记 | 第十站（获取云原生旅行秘籍）
• 

  罗汉果几天喝一次最好呢
• 

  不怕水的胶水有哪些
• 

  老黄历：2021年12月9日适合订婚吗,十一月初六这天如何？
• 

  mysql的数据库文件有几种?以及扩展名 mysql数据文件扩展
• 

  麻辣蒜香煎豆腐的制作方法 麻辣蒜香煎豆腐怎么做
• 

  胎压不足指示灯是什么情况? 胎压不足的指示灯
• 

  猪笼草有毒吗?猪笼草养在室内好不好 猪笼草中的水有毒吗
• 

  白面板|如何俘获小姐姐的心？魅族纯白色设计你有必要了解一下
• 

  饺子皮除了包饺子还能做什么好吃的
• 

  能遇见你，真是太好了
• 

  下雪天公交车会停运，公交车下雪天为啥不滑
• 

  怎样设置sim卡密码
• 

  搜狗输入法如何设置显示界面？
• 

  手机大亨2怎么开启x屏幕
• 

  z95
• 

  家公家婆是指什么关系

• c语言|《伏C录》凝丹篇-函数栈帧理解手册
• c语言|《伏C录》凝气篇-初战动态内存管理四兄弟
• c语言|《伏C录》破劫篇-零基础无境界限制极速领悟指针与数组
• c语言|C语言实现扫雷（含展开，附源码）
• c语言|《伏C录》神兵百解篇-重铸struct关键字之心
• Linux|Linux命令pwd的自我实现
• 算法|2021年图灵奖，花落高性能计算先驱、田纳西大学教授Jack Dongarra
• 数据结构与java集合|java集合图解源码系列【4】（从HashMap讲到红黑树和哈希表）
• 求解COP 5536