前言
经过前面的学习，咋们已经学完了链表相关知识，这时候不妨来几道链表算法题来巩固一下吧！
如果有不懂的可翻阅之前文章哦！
个人主页：小八哥向前冲~-CSDN博客
数据结构专栏：数据结构【c语言版】_小八哥向前冲~的博客-CSDN博客
c语言专栏：c语言_小八哥向前冲~的博客-CSDN博客
这里的题目都是非常经典的好题目哦！能让我们对链表的理解更深一步！
当然，有些题目非常有意思哦！哈哈哈哈！我们一起来看看！
目录
前言
1.反转链表
2.删除链表节点
3.寻找中间节点
4.环形链表的约瑟夫问题
5.合并有序链表
6.输出倒数k节点
7.链表的回文结构
8.判断相交链表
9.环形链表
10.环形链表2
11.随机链表的复制
1.反转链表
题目
给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
题目详情：LCR 024. 反转链表 - 力扣（LeetCode）
思路
看到这道题是不是觉得稳了？是不是觉得很简单？
我们只需要一个一个节点遍历链表，将一个个节点按顺序拿下来头插不就行了！
上图理解：
代码
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head){
ListNode*newhead=NULL,*cur=head;
//头插
while(cur)
{
ListNode*next=cur->next;
cur->next=newhead;
newhead=cur;
cur=next;
}
return newhead;
}思路2
创建哨兵位节点，将原链表遍历，把每个链表一个一个尾插到哨兵位的后面。
是不是也很简单？上图理解一下：
代码
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head){
ListNode*cur=head;
//创建哨兵位节点
ListNode*newhead=(ListNode*)malloc(sizeof(ListNode));
newhead->next=NULL;
while(cur)
{
ListNode*next=cur->next;
cur->next=newhead->next;
newhead->next=cur;
cur=next;
}
return newhead->next;
}2.删除链表节点
题目
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
详情：LCR 136. 删除链表的节点 - 力扣（LeetCode）
思路
创建一个哨兵位，遍历原链表，将不是指定节点全部拿下来尾插，得到新的链表！
上图解释一下：
代码
typedef struct ListNode ListNode;
struct ListNode* deleteNode(struct ListNode* head, int val){
ListNode*newhead=(ListNode*)malloc(sizeof(ListNode));
ListNode*tail=newhead;
ListNode*cur=head;
while(cur)
{
if(cur->val!=val)
{
tail->next=cur;
tail=cur;
}
cur=cur->next;
}
tail->next=NULL;
return newhead->next;
}3.寻找中间节点
题目
给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
详情：876. 链表的中间结点 - 力扣（LeetCode）
思路
定义两个指针（快慢指针），快指针走两步，慢指针走一步，最终慢指针便是中间节点！但是需要分奇数链表和偶数链表。
上图：
代码
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode*slow,*fast;
//快慢指针，慢指针走一步，快指针走两步
slow=fast=head;
while(fast&&fast->next)//两种情况,一种节点为奇数，一种节点为偶数
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}4.环形链表的约瑟夫问题
题目
详情：环形链表的约瑟夫问题_牛客题霸_牛客网 (nowcoder.com)
思路
1.创建链表节点
2.将节点连成环
3.开始纱人
图：
代码
typedef struct ListNode ListNode;
//创建链表节点函数
ListNode*Buynode(int x)
{
ListNode*node=(ListNode*)malloc(sizeof(ListNode));
node->val=x;
node->next=NULL;
return node;
}
//将节点连成环，创建循环链表
ListNode* NodeCircle(int n)
{
//先创建第一个节点
ListNode*phead=Buynode(1);
ListNode*ptail=phead;
for(int i=2;i<=n;i++)
{
ptail->next=Buynode(i);
ptail=ptail->next;
}
ptail->next=phead;//将节点连起来
return ptail;
}
int ysf(int n, int m ) {
// write code here
ListNode*prev=NodeCircle(n);
ListNode*pcur=prev->next;
int count=1;
while(pcur->next!=pcur)//最后只剩一个人，它的下一个节点是它自己
{
if(count==m)//数到m就自杀
{
prev->next=pcur->next;
free(pcur);
pcur=prev->next;
count=1;//当杀完后，置为1，重新数数
}
else
{
//没数到m就开始数（挪prev和pcur位置）
prev=pcur;
pcur=pcur->next;
count++;
}
}
return pcur->val;
}5.合并有序链表
题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
详情：21. 合并两个有序链表 - 力扣（LeetCode）
思路
同时遍历两个链表和创建一个哨兵位，每个节点每个节点进行比较，小的那个节点尾插到带头哨兵后面，注意当其中有一个为空时，则另一个还未尾插完！
上图理解：
代码
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
ListNode*l1=list1;
ListNode*l2=list2;
ListNode*newhead,*newtail;
newhead=newtail=(ListNode*)malloc(sizeof(ListNode));//哨兵节点
while(l1&&l2)
{
if(l1->val<l2->val)
{
//将l1拿下来尾插
newtail->next=l1;
newtail=newtail->next;
l1=l1->next;
}
else
{
//将l2拿下来尾插
newtail->next=l2;
newtail=newtail->next;
l2=l2->next;
}
}
//跳出循环有两种情况,要么l1没尾插完，要么l2没尾插完
if(l1==NULL)
{
newtail->next=l2;
//newtail=newtail->next;
}
if(l2==NULL)
{
newtail->next=l1;
//newtail=newtail->next;
}
return newhead->next;
}6.输出倒数k节点
题目
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
思路
定义快慢指针，但这里的快慢指针并不是和寻找中间节点那个快慢指针一样！听我道来。
这里要找倒数第几个节点，快指针就先走几个节点！随后一起俩指针一起走。当快指针走到空时，慢指针指向的就是倒数k节点！
图：
代码
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k){
//定义快慢指针，快指针开始就比满指针快k步，随后一直一步一步走
ListNode*slow=head,*fast=head;
while(k--)
{
fast=fast->next;
}
//随后一起走，当快指针走到空，慢指针就是那个节点
while(fast)
{
fast=fast->next;
slow=slow->next;
}
return slow->val;
}
7.链表的回文结构
题目
给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
详情：LCR 027. 回文链表 - 力扣（LeetCode）
注意：这题目很经典很重要！需要掌握！
思路
先找到中间节点，再反转中间节点之后的节点！定义俩个指针一个头指针，一个中间节点指针。
俩指针同时遍历比较，途中但凡没有相同的就不是回文结构！
是不是觉得很简单？没错，其实主要就掌握链表的反转和寻找链表的中间节点就行！
上图：
代码
typedef struct ListNode ListNode;
//寻找中间节点函数
ListNode*MidNode(ListNode*head)
{
//快慢指针
ListNode*slow=head,*fast=head;
//慢指针走一步，快指针走两步
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
//慢指针就是中间节点
return slow;
}
//翻转节点函数
ListNode*reverse(ListNode*head)
{
ListNode*newhead=NULL,*cur=head;
while(cur)
{
ListNode*next=cur->next;
cur->next=newhead;
newhead=cur;
cur=next;
}
return newhead;
}
bool isPalindrome(struct ListNode* head){
ListNode*mid=MidNode(head);
ListNode*head1=head;
ListNode*head2=reverse(mid);
while(head2&&head1)
{
if(head1->val!=head2->val)
{
return false;
}
head1=head1->next;
head2=head2->next;
}
return true;
}8.判断相交链表
题目
给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
详情：LCR 023. 相交链表 - 力扣（LeetCode）
思路
分别遍历俩链表且计算俩链表的长度。如果最后一个节点（地址）相同（注意这里不要用值比较，可能不是一个节点只是值相同而已！），计算出长的链表，先走相差步（俩链表相减的绝对值）。
最终同时遍历，一直比较，直到比较到俩链表的相同节点，就找到了相交节点！
代码
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
ListNode*curA=headA,*curB=headB;
int lenA=0,lenB=0;
while(curA->next)
{
lenA++;
curA=curA->next;
}
while(curB->next)
{
lenB++;
curB=curB->next;
}
if(curA!=curB)
{
return NULL;
}
int tmp=abs(lenA-lenB);
ListNode*shortList=headA,*longList=headB;
if(lenA>lenB)
{
shortList=headB;
longList=headA;
}
while(tmp--)
{
longList=longList->next;
}
while(shortList!=longList)
{
shortList=shortList->next;
longList=longList->next;
}
return shortList;
}9.环形链表
题目
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
详情：141. 环形链表 - 力扣（LeetCode）
思路
定义快慢指针，慢指针走一步，快指针走两步，如果没有环就是寻找中间节点的情景，如果有环，因为有速度差又是闭合的环状，最终会追到！
代码
bool hasCycle(struct ListNode *head) {
struct ListNode*slow=head,*fast=head;
//如果没有环，分奇数偶数情况，奇数fast->next为空，偶数fast为空
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
return true;
}
}
return false;
}拓展
俩个问题：
- 一定会追到吗？有没有可能会错过？请证明一下！
- 如果快指针走3步呢？还追得上吗？如果慢指针走俩步呢？又追不追得上？
第一个问题解答
一定会追上！慢指针走一步，快指针走俩步一定会追上！
慢指针走一步，快指针走俩步，它们的相对速度其实就是一步！什么意思呢？它们之间的距离会一步一步的减少，就是因为是一步一步的减少才不会错过！
第二个问题解答
如果快指针走三步，慢指针走一步的话，不一定能追上！因为它们的相对速度是2步，可能会错过！
如果当慢指针进环时，快指针和慢指针的距离如果是偶数的话，就能追上！
如果当慢指针进环时，快指针和慢指针的距离如果是奇数的话，就错过了！那么开始第二圈的追逐！当开始追的时候，它们的距离如果是偶数，第二圈就追上了！如果是奇数，第二圈追不上，那么之后永远追不上！
上图解释一下第二个问题：
10.环形链表2
题目
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
详情：142. 环形链表 II - 力扣（LeetCode）
思路1
仍然定义快慢指针，快指针走俩步，慢指针走一步，最终会追到一起！
再将追到一起的节点和头节点一起遍历，当俩指针相等时则就是环链表的入口节点。
你是不是有疑问？为什么俩指针相等时就是环链表的入口节点？
我们上图解释一下：
代码
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode*slow=head,*fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
struct ListNode*meet=slow;
struct ListNode*cur=head;
while(meet!=cur)
{
meet=meet->next;
cur=cur->next;
}
return cur;
}
}
return NULL;
}思路2
还是定义快慢指针，慢指针走一步，快指针走俩步，最终终会追上！
将相逢节点断开，然后就变成了俩个链表，问题变成了在相交链表中寻找相交节点！
上图：
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode*Intersect(struct ListNode*head1,struct ListNode*head2)
{
struct ListNode*cur1=head1,*cur2=head2;
int len1=0,len2=0;
while(cur1)
{
cur1=cur1->next;
len1++;
}
while(cur2)
{
cur2=cur2->next;
len2++;
}
int tmp=abs(len1-len2);
struct ListNode*shortList=head1,*longList=head2;
if(len1>len2)
{
longList=head1;
shortList=head2;
}
//长的先走相差步
while(tmp--)
{
longList=longList->next;
}
while(longList!=shortList)
{
longList=longList->next;
shortList=shortList->next;
}
return longList;
}
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode*slow=head,*fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
//将环拆开，变成寻找两链表的中间节点
fast=fast->next;
slow->next=NULL;
return Intersect(fast,head);//寻找两链表的中间节点
}
}
return NULL;
}11.随机链表的复制
题目
详情：138. 随机链表的复制 - 力扣（LeetCode）
思路
1.遍历原链表，一个一个创建新节点连接到原节点的后面！
2.再遍历原链表，按照原链表randrom的连接来连接新节点！
3.再遍历，从原链表上面拆解新链表下来！（尾插）
图文理解：
代码
struct Node* copyRandomList(struct Node* head) {
struct Node*cur=head;
while(cur)
{
//拷贝节点插入在原节点的后面
struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
copy->val=cur->val;
copy->next=cur->next;
cur->next=copy;
cur=copy->next;
}
//给拷贝节点的random赋值
cur=head;
while(cur)
{
struct Node*copy=cur->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
//控制random的值
copy->random=cur->random->next;
}
cur=copy->next;
}
//将拷贝节点拆下来（尾插）
cur=head;
struct Node*newhead=NULL,*newtail=NULL;
while(cur)
{
struct Node*copy=cur->next;
struct Node*next=copy->next;
if(newhead==NULL)
{
newhead=newtail=copy;
}
else
{
newtail->next=copy;
newtail=newtail->next;
}
//恢复原链表结构,也可以不恢复
cur->next=next;
cur=next;
}
return newhead;
}今天的算法题就分享到这里吧！这些题目都是很经典的哦！
我们下期见！
