Day4——两两交换链表节点、删除链表第n个绩点、链表相交、环形链表||
今天是算法训练的第四天。
目录
前言
一、两两交换链表节点
解题思路
二：删除链表第n个绩点
1、解题思路
三、链表相交
1、解题思路
四、环形链表||
解题思路：
总结
前言
今日文案：
喷泉之因此美丽，是正因水有了压力。瀑布之因此壮观，是正因水有了落差。人的成长和进步也一样，人没有压力，潜能得不到开发，智慧就不能开花，最大的损失还是自我。偶尔给自我一点压力，适时让自我绽放一次，你会发现其实自我很优秀，很超凡。
一、两两交换链表节点
题目描述：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
题目来源：
力扣
解题思路
要操控两个相邻节点反转，就是把他们的连接改变，看图：
那要改变指向，我们一定要注意保存好地址，不然一不小心就不见了。
代码如下：
struct ListNode* swapPairs(struct ListNode* head){
struct ListNode*dummyhead=(struct ListNode*)malloc(sizeof(struct ListNode));
dummyhead->next=head; //创建一个虚拟头节点，然后改变后面两个的位置，不用考虑头节点问题
struct ListNode*cur=dummyhead; //先站在头节点
while(cur->next&&cur->next->next) //一定要先判段cur->next，不然会出错
{
struct ListNode*temp1=cur->next; //保存好位置，为下面跳转做准备
struct ListNode*temp2=cur->next->next->next;
cur->next=cur->next->next;
cur->next->next=temp1;
temp1->next=temp2;
cur=cur->next->next;
}
return dummyhead->next; //返回的头节点
}画图多看几遍总能理解的，加油！建议去代码随想录看看，卡哥的动态图很好，我这做不出来，纯粹学习笔记，不好意思哈~
二：删除链表第n个绩点
题目描述：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
题目来源：
力扣
1、解题思路
快慢指针是重点！
假设我们要删除倒数第二个点，图解：
代码如下：
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
struct ListNode*dummyhead=(struct ListNode*)malloc(sizeof(struct ListNode));
dummyhead->next=head;
struct ListNode* fast=dummyhead;
struct ListNode* slow=dummyhead; //虚拟头节点开始，不用判断头节点问题
n=n+1; //因为从虚拟节点开始，走多一步才行
while(n--&&fast)
{
fast=fast->next; //fast移动n步
}
while(fast)
{
slow=slow->next; //当fast指向0，结束
fast=fast->next;
}
slow->next=slow->next->next; //删除（后面还应该手动释放内存呦，做题就不需要而已）
return dummyhead->next;
}三、链表相交
题目描述：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
题目来源：
力扣
1、解题思路
我们最先要注意的一个点是，相交是指地址一样，而不是里面的值一样。
那一长一短的两个链表，我们要怎么算呢，先对齐！对齐之后我们再一步一步遍历去判定是否相等，因为长链表多出来那一部分肯定是在节点之前的，可以先放掉，判断后面的。
如图（来自代码随想录）：
代码如下：
struct ListNode *myfing(struct ListNode *p1,struct ListNode *p2)
{
while(p1) //比较地址
{
if(p1==p2) //如果地址相等，那就返回
return p1;
else
{
p1=p1->next; //不相等继续走下去，直到为0，也就是不相交的情况
p2=p2->next;
}
}
return NULL;
}
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode * w=0;
struct ListNode *p1=headA,*p2=headB;
int length_a=0,length_b=0,s=0;
while(p1) //找出两个链表的长度
{
length_a++;
p1=p1->next;
}
while(p2)
{
length_b++;
p2=p2->next;
}
p1=headA;
p2=headB;
if(length_a>length_b) //然后移动到一起开始的地方
{
s=length_a-length_b;
while(s--)
{
p1=p1->next;
}
w=myfing(p1,p2);
}
else
{
s=length_b-length_a;
while(s--)
{
p2=p2->next;
}
w=myfing(p1,p2);
}
return w;
}四、环形链表||
题目描述：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
题目来源：
力扣
解题思路：
这个题真的太精妙了，直接看题解，醍醐灌顶hhh。
这里直接上代码了：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode *fast=head; //快慢指针
struct ListNode *slow=head;
while(fast&&fast->next)
{
fast=fast->next->next; //fast一次走两步，slow一次走一步，进入循环后等于每次一步接近
slow=slow->next;
if(fast==slow) //快慢指针相遇时
{
struct ListNode *p2=fast; //记录位置
struct ListNode *p1=head;
while(p1!=p2) //遍历到两个指针相遇
{
p1=p1->next;
p2=p2->next;
}
return p1; //返回入口值
}
}
return 0; //无入口返回0.
}加油，继续学习。
总结
写得不好，请多指教。希望每天进步一点点，冲冲冲。