首页 1 2 3 4 5 6 7

【链表OJ】相交链表环形链表1

前言:

💥🎈个人主页:Dream_Chaser～ 🎈💥

✨✨刷题专栏:http://t.csdn.cn/UlvTc

⛳⛳本篇内容:力扣上链表OJ题目

一.leetcode 160. 相交链表

1.问题描述:

2.解题思路:

二.leetcode 141.环形链表

1.问题描述:

2.代码思路:

3.问题证明:

一.leetcode 160. 相交链表

来源:160. 相交链表 - 力扣（LeetCode）

1.问题描述:

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回NULL 。

图示两个链表在节点c1开始相交：

已知a1与b1的头结点地址，并分别用headA和headB指针指向

题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

题目接口:

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{}

2.解题思路:

原始链表：

首先定义tailA和tailB分别遍历a链表和b链表,在遍历过程中，分别求出两链表长度,分别定义为lenA和lenB,然后用lenA和lenB相减取差的绝对值，计为差距步gap

然后定义指向长链表的指针longList,和指向短链表的指针shortList，用前面定义的LenA和LenB比较它们的长度,进行合适赋值，接着让长的链表走差距步gap。若长链表结点的地址不等于短链表，则让tailA和tailB指针继续走，有相等结点则跳出循环，返回此时的longList或者shortList。

实现代码:

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{struct ListNode* tailA = headA;struct ListNode* tailB = headB;int lenA = 1, lenB = 1;//原始长度定义为1才是正确的while (tailA){tailA = tailA->next;lenA++;}while (tailB){tailB = tailB->next;lenB++;}if (tailA != tailB)//若两指针到结束也找不到相等结点，则返回NULLreturn NULL;int gap = abs(lenA - lenB);//取出两者相减的绝对值，赋值给gap表示两链表的差距步struct ListNode*longList = headA;//先假定A链表为长链表struct ListNode* shortList = headB;if (lenA < lenB)//接着两链表比较，如果满足此条件，则重新赋值，定义B链表的为长链表{longList = headB;shortList = headA;}while (gap--)//长链表先走差距步{longList = longList->next;}while (longList != shortList)//若没有相等(地址相等)则继续遍历{longList = longList->next;shortList = shortList->next;}return shortList;
}

代码执行:

二.leetcode 141.环形链表

1.问题描述:

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

题解接口:

bool hasCycle(struct ListNode *head) {}

2.代码思路:

本题的代码思路:

定义一个快指针,让其先走两步,接着定义一个慢指针，一次走一步，反复此循环。

如果快慢指针指向的地址相等，则证明链表中存在环。
如果快指针提前指向NULL，循环结束，则证明不是环形链表，直接返回false。

函数实现

bool hasCycle(struct ListNode *head) {struct ListNode* fast=head,*slow =head;while(fast && fast->next){fast=fast->next->next;//快指针先走两步,慢指针走一步slow=slow->next; //慢指针走一步if(fast==slow)//指针相遇表明链表带环{return true;}}return false;//否则返回NULL
}

代码执行:

然而本题的重点在于如何证明上面的代码的实现逻辑，是一个数学问题。

3.问题证明:

1、slow和fast一定会相遇吗?

答:一定会

画一张图来证明一下, 此时两指针同时指向头节点的地址。

接着先让快指针fast=fast->next->next(快指针先走两步),后让 slow=slow->next(慢指针走一步).

fast会先进环，slow会后进环，假设slow进环时，slow和fast之间的距离为N

slow进环以后，fast开始追击slow,slow每走1步，fast每走2步，他们之间距离缩小1。

2、slow走1步，fast走n(3/4/5….)步可以吗?(n > 2)

不一定

举例:

slow每次走一步，fast每次走三步，它们一定可以相遇吗？答:不一定。

画图

当快慢指针之间的距离个数为奇数时

fast会先进环，slow会后进环，假设slow进环时， slow和fast之间的距离为N

slow进环以后，fast开始追击slow，slow每走1步，fast每走3步，他们之间距离缩小2

当快指针追赶上慢指针时,此时错过了,并进入新一轮的追击,假设一个值C为环的长度,那么快慢指针的距离此时必为C-1

所以,如果C-1是奇数那么fast永远追不上slow

当C-1的距离为偶数时,那么此时的距离变化为

N N-2 N-4 ... 4 2 0 ，0则表示此时两指针相遇，表明下一轮可以追上。