【数据结构 C语言版】第三篇 单链表习题_数据结构c语言 单链表题
方法一代码题解（方法二）（1）翻转方向（2）代码实现细节图解方法二代码。
方法一代码
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）翻转方向
（2）代码实现细节图解
方法二代码
struct ListNode\* reverseList(struct ListNode\* head){
struct ListNode\* n1,\*n2,\*n3;
//防止链表为空n3赋值放在循环里面
n1=NULL,n2=head,n3=NULL;
while(n2)
{
n3=n2->next;
n2->next=n1;
//迭代
n1=n2;
n2=n3;
}
return n1;
}
3.链表的中间结点
题目
题解
(1)通过快慢指针，可以只遍历一遍链表就能得出正确答案
(2)快指针一次走两步，慢指针一次走一步，快指针走完链表，慢指针刚好在一半处。
(3)图解
代码
struct ListNode\* middleNode(struct ListNode\* head){
//快慢指针
struct ListNode\* f=head,\*s=head;
//注意两个判断条件
while(f&&f->next)
{
s=s->next;
f=f->next->next;
}
return s;
}
4. 链表中倒数第k个结点
题目
[链表中倒数第k个结点_牛客题霸_牛客网 ](链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com))
题解
（1）方法还是快慢指针
（2）fast先走一步，fast跟slow再同时走,最后slow停在的地方就是倒数第一个。
类推，fast先走k步，fast跟slow再同时走,最后slow停在的地方就是倒数第几个。
（3）图解：
注意
(1)为什么fast先走的循环中使用k–,使用–k可以吗?
代码while(k–),k–的含义：每次先用k，然后再自减。每次循环k的变化（以上图为例）：3,2,1。当k==0的时候不执行。
当while(–k)时,–k的含义：每次用k的时候先自减。k的变化：2,1。导致就执行两次。
（2）链表可能为空需要判断。
代码
struct ListNode\* FindKthToTail(struct ListNode\* pListHead, int k ) {
struct ListNode \*fast,\*slow;
fast=slow=pListHead;
//fast先走n步
while(k--)
{
//当链表为空的时候，返回空值
if(!fast)
{
return fast;
}
fast=fast->next;
}
//fast跟slow一直走到fast为空的时候
while(fast)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}
5.合并两个有序链表
题目
题解
（1）写一个哨兵头，比大小，小的只管尾插，不需要考虑头插。
（2）图解
代码
struct ListNode\* mergeTwoLists(struct ListNode\* list1, struct ListNode\* list2){
struct ListNode\* guard =(struct ListNode\*)malloc(sizeof(struct ListNode));
struct ListNode\* cur1,\*cur2,\*newhead,\*cur3;
guard->next=NULL;
cur1=list1,cur2=list2,newhead=cur3=guard;
//小的尾插
while(cur1&&cur2)
{
if(cur1->val>=cur2->val)
{
cur3->next=cur2;
cur3=cur3->next;
cur2=cur2->next;
}
else
{
cur3->next=cur1;
cur3=cur3->next;
cur1=cur1->next;
}
}
//剩余的尾插
if(cur1)
{
while(cur1)
{
cur3->next=cur1;
cur3=cur3->next;
cur1=cur1->next;
}
}
else
{
while(cur2)
{
cur3->next=cur2;
cur3=cur3->next;
cur2=cur2->next;
}
}
//释放哨兵结点，更新newhead的位置
newhead=guard->next;
free(guard);
return newhead;
}
6.给定值x为基准将链表分割
编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结
点之前
题目
[链表分割](链表分割_牛客题霸_牛客网 (nowcoder.com))
题解
（1）创建两个哨兵结点，一个哨兵结点（暂且叫它lessGuard）后面插入的是小于x值的结点，另一个哨兵结点（叫它greaterGuard）后面插入的是大于x值的结点。
(2)过程图解：
注意
（1)greaterGuard指向的那条链表最后一个结点的next为什么要处理？
如果greaterGuard指向的那条链表的最后一个结点在原链表中不是最后一个结点的话，那么就会指向lessGuard指向的链表中的最后一个结点，如图所示：
两个链表合并的话就会出现下面这张图的情况，即形成一个环：
代码
ListNode\* partition(ListNode\* pHead, int x) {
// write code here
//lessGuard:小于x的结点的链表的哨兵头,lessTail:用于操作链表
//greaterGuard:大于x的结点的链表的哨兵头，greaterTail:用于操作链表
//tail用于遍历原链表
struct ListNode \*lessGuard,\*lessTail,\*greaterGuard,\*greaterTail,\*tail;
lessGuard=(struct ListNode\*)malloc(sizeof(struct ListNode));
greaterGuard=(struct ListNode\*)malloc(sizeof(struct ListNode));
lessTail=lessGuard;
greaterTail=greaterGuard;
tail=pHead;
//结点根据大小尾插到相应的链表后面
while(tail)
{
if(tail->val<x)
{
lessTail->next=tail;
tail=tail->next;
lessTail=lessTail->next;
}
else
{
greaterTail->next=tail;
tail=tail->next;
greaterTail=greaterTail->next;
}
}
//最后两个链表合并
lessTail->next=greaterGuard->next;
//greaterTail->next后面应该是NULL
//否则可能形成环
greaterTail->next=NULL;
pHead=lessGuard->next;
//释放掉两个哨兵结点
free(greaterGuard);
free(lessGuard);
return pHead;
}
7. 链表的回文结构
题目
[链表的回文结构](链表的回文结构_牛客题霸_牛客网 (nowcoder.com))
题解
(1)可以先用快慢指针，找出链表的中间点，然后将后半段链表反转，最后两个链表进行比较。
(2)这题可以看成是第2题与第3题的结合。
(3)图解
代码
bool chkPalindrome(ListNode\* A) {
// write code here
struct ListNode\* f,\*s;
f=s=A;
while(f&&f->next)
{
f=f->next->next;
s=s->next;
}
struct ListNode \*cur=s, \*n = NULL;
while(cur)
{
struct ListNode\* next=cur->next;
cur->next=n;
n=cur;
cur=next;
}
struct ListNode \*cur1=A;
while(n&&cur1)
{
if(n->val!=cur1->val)
{
return false;
}
n=n->next;
cur1=cur1->next;
}
return true;
}
8.相交链表
输入两个链表，找出它们的第一个公共结点。
题目
题解
（1）a.先可以遍历一遍，如果两个链表尾结点的地址相同就说明两个链表相交。反之，则不想交。
b.通过a步骤的遍历，分别求出两个链表的长度，然后 长度长的链表先走差距步（两个链表的长度差）。走完之后，同时走，第一个地址相等的结点就是相交结点。
（2）图解：
代码
struct ListNode \*getIntersectionNode(struct ListNode \*headA, struct ListNode \*headB) {
//1.分别遍历
struct ListNode\* curA,\*curB;
curA=headA,curB=headB;
//遍历判断条件是结点下一个不为空
//防止空结点
if(headA==NULL||headB==NULL)
{
return NULL;
}
//len要从1开始
int lenA=1,lenB=1;
while(curA->next)
{
lenA++;
curA=curA->next;
}
while(curB->next)
{
lenB++;
curB=curB->next;
}
//如果不相等就返回空
if(curA!=curB)
{
return NULL;
}
//2.长的走差距步
//默认长链表是A,短链表是B（可以少写判断）
struct ListNode\* longList = headA,\*shortList = headB;
if(lenB>lenA)
{
longList=headB;
shortList=headA;
}
//差距步总不能是负的吧
int gap = abs(lenA-lenB);
while(gap--)
{
longList=longList->next;
}
//3.开始同时走
while(longList!=shortList)
{
longList=longList->next;
shortList=shortList->next;
}
return longList;
}
9.判断链表中是否有环
给定一个链表，判断链表中是否有环。
题目
题解
（1）快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，
如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。
（2）注意：这题切不能遍历，一遍历就死循环。
（3)图解：
注意
关于这题的问题请看这篇文章：深入理解快慢指针算法 – 链表环路检测 - 知乎 (zhihu.com)
代码
bool hasCycle(struct ListNode \*head) {
struct ListNode\* fast,\*slow;
fast=slow=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(fast==slow)
return true;
}
return false;
}
10. 返回链表开始入环的第一个结点
给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL
题目
题解：
既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上大数据知识点，真正体系化！
由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新
ast->next->next;
if(fast==slow)
return true;
}
return false;
}
###### 10. 返回链表开始入环的第一个结点
给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL
>
> 题目
>
>
>
[142. 环形链表 II](https://bbs.csdn.net/topics/618545628)
>
> 题解：
[外链图片转存中...(img-t7vwHYbP-1714447308416)]
[外链图片转存中...(img-cqxYG7f5-1714447308417)]
[外链图片转存中...(img-hAkXayno-1714447308417)]
**既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上大数据知识点，真正体系化！**
**由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新**
**[需要这份系统化资料的朋友，可以戳这里获取](https://bbs.csdn.net/topics/618545628)**
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
15
0- 0
已为社区贡献4条内容
所有评论(0)