数据结构链表力扣例题AC（3）——代码以及思路记录

160. 相交链表

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

AC写法一

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//思路基本一样struct ListNode* curA = headA;struct ListNode* curB = headB;int lenA = 0,lenB = 0;//先计算两个的长度while(curA){curA = curA->next;lenA++;}while(curB){curB = curB->next;lenB++;}//遍历结束后回到头结点curA = headA;curB = headB;//计算差距，并开始走差距步,diff大小可以知道哪一个更长int diff = lenA - lenB;if(diff > 0) {while(diff > 0) {curA = curA->next;diff--;}} else if(diff < 0) {while(diff < 0) {curB = curB->next;diff++;}}//当两个不相等就继续走，但是要注意任意一个都不能为空while(curA && curB && curA != curB){curA = curA->next;curB = curB->next;}//如果没有相交，两个也都走到了空//如果相交了此刻停留的位置也正好是相交初始节点，直接返回return curA;
}

AC写法二

struct ListNode* curA = headA;struct ListNode* curB = headB;int lenA = 0,lenB = 0;//lenA和lenB最后计数都会少了一个//但这道题目的是为了计算差值//同时都少一个不会对结果有影响while(curA->next){curA = curA->next;lenA++;}while(curB->next){curB = curB->next;lenB++;}//如果尾节点不相同，就没有相交。直接返回if(curA != curB){return NULL;}//abs函数，计算绝对值int n = abs(lenA - lenB);struct ListNode* longList = headA, *shortList = headB;//上一步做了假设，如果假设不成立那就交换，后边就不用关心长的是哪条链表了if(lenB > lenA){longList = headB;shortList = headA;}//长的先走差距步while(n--){longList = longList->next;}while(longList != shortList){longList = longList->next;shortList = shortList->next;return longList;

代码思路

上述两种代码的基本思路是一样的，具体细微的差别已经标注在代码中，接下来进行陈述：

首先看题寻找相交节点，那么这个链表不可能是 X 型，因为节点只能存储一个节点地址，所以只能是 Y 型或者不想交是平行，这一点看题目就可以明白。

最容易想到的暴力法，双指针，一个指向链表A，一个指向链表B，lenA进行链表A的遍历，将每一个节点与lenB当前所指的节点进行比较看是否相等，都不相等则lenB指向下一个LenA再进行比较，这样的方法时间复杂度为O(N^2)

还有一种时间复杂度为O(N)的方法。观察 Y 型结构，假设有两个指针指向两条链表的开始同时开始走并进行比较，由于链表相交前长度可能不一样，不一样的时候两个指针不可能相遇，但如果要两个指针相遇，相交之前有部分必须对应，那现在就是解决如何使两个指针按照我们需要的对应起来了，当较长的链表先走，走到剩余部分和较短链表一样时，两个指针一起走就解决了这个问题，而这部分先走的就是两条链表的长度差，所以两个指针都遍历一遍链表得出各自长度（遍历的同时可以比较尾节点是否相同，不相同直接说明没有相交），然后相减得出长度差，就可以实现如有交点两个指针一定会相遇的情况了。

141. 环形链表

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

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

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

AC

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

代码思路

快慢指针绝绝绝绝绝绝！

环形链表难点在于不知道哪里开始的环，但是在环里，就没有前后之分，使用快慢指针，从头开始走，fast走两步slow走一步，当fast走进环的时候slow一定还在后边，但是当slow也进环以后，由于两者速度不一样，fast会追上slow，想象一下速滑运动中的套圈，而在环中的话，就一定会相遇。如果没有环，那么fast会指向空。只要思路正确并不难写。至于为什么while循环中还需要fast->next也不能为空，因为fast一次走两步，当fast指向尾节点的时候，没有fast->next->next.

为什么快指针每次走两步，慢指针走一步可以？

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚 进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。 此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情 况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

快指针一次走3步，走4步，...n步行吗？

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不允许修改 链表。

AC

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;while(head != meet){head = head->next;meet = meet->next;}return meet;}}return NULL;
}

代码思路

说明：

        H为链表的起始点，E为环入口点，M与判环时候相遇点

设：

        环的长度为R,H到E的距离为L E到M的距离为X

        则：M到E的距离为R-X

在判环时，快慢指针相遇时所走的路径长度：

        fast：L+X + nR

        slow：L + X

注意：

        1.当慢指针进入环时，快指针可能已经在环中绕了n圈了，n至少为1

        因为：快指针先进环走到M的位置，最后又在M的位置与慢指针相遇

        2.慢指针进环之后，快指针肯定会在慢指针走一圈之内追上慢指针

        因为：慢指针进环后，快慢指针之间的距离最多就是环的长度，而两个指针在移动时，每次它们至今的距离都缩减一步，因此在慢指针移动一圈之前快指针肯定是可以追上慢指针的

而快指针速度是满指针的两倍，因此有如下关系是：

        2 * (L + X)=L + X + nR

        L+X = nR

        L = nR - X (n为1,2,3,4..，n的大小取决于环的大小，环越小n越大)

        极端情况下，假设 n=1,此时：L = R -X

即：一个指针从链表起始位置运行，一个指针从相遇点位置绕环，每次都走一步，两个指针最终会在入口点的位置相遇

思路二：将meet的下一个节点meet->next交给一个新指针newhead，然后将meet的next置空，meet->next = NULL，此刻就将题转化为了链表相交问题，但是这种写代码更为复杂，此处不做尝试