题型三：链表相交，找相交节点
思路解析
看到这类题型首先要判断链表是否相交，而相交条件：两链尾部节点相同（地址相同，val值相同，next相同）。这样我们便可找到两链表的尾节点并判断这两个节点地址是否相同，若相同则两链表相交。上面这种情况两链表呈'Y'型，那么我们想一下两链表相交是否可以呈'X'型呢？
如上图所示如果两链表相交呈'X'型的话，相交节点的next就会指向两个节点，这并不符合单链表的定义。
那么在判断了相交链表后，如何找到相交节点呢？在我们找尾节点时，我们可以顺便计算两链表的长度，定义两链表指针slow，fast分别指向链表头节点，让指向长链表的指针先走两链表长度的差值，然后一起向后走，当slow == fast时就找到了相交节点。
OJ题实例
LeetCode链接: 160. 相交链表
解题代码
//方法一的解法 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* cur1 = headA, *cur2 = headB; int len1 = 1, len2 = 1; //找尾节点，并计算链表长度 while(cur1 -> next) { cur1 = cur1->next; len1++; } while(cur2 -> next) { cur2 = cur2->next; len2++; } if(cur1 != cur2) return NULL; //计算链表长度差值 int count = abs(len1 - len2); struct ListNode* slow=headA, *fast=headB; if(len1 > len2) { fast = headA; slow = headB; } //找相交节点 while(count--) fast = fast->next; while(slow != fast) { slow = slow->next; fast = fast->next; } return slow; }
题型四：链表带环，找入环节点
思路解析
解决这题我们还是要先定义快慢指针slow，fast，即当slow向后走一步，fast向后走两步。我们便可写一个结束条件为fast && fast->next的循环。因为如果此链表不带环，那么指针迟早会走到NULL；如果链表带环，那么便没有空节点，此循环便不会结束。这时我们只需要在slow == fast时结束循环，因为只有环形结构slow才能追上fast，则链表带环且这点在环内为相遇点。
对于找入环的第一个节点，我们可以先假设C为环长，L为环外面部分长，X为入环点到相遇节点的长，n为两指针相遇时fast比slow多走的圈数，此处长皆为节点数，那么我们便可得到如下图所示的结构图：
接下来我将以两种方法解决此问题：
方法一：
我们可以想到当两节点相遇时，慢指针slow走过了L + X的距离，快指针fast走过了L + nC + X距离，又因为快指针的速度是慢指针的2倍，于是我们得到了一个数学公式，即：2(L + X) = L + nC + X，经过化简最后得到L = nC - X。此时我们可以定义两个结构体指针head，meet让他们分别从链表头节点和相遇节点向后走，根据此公式他们会在入环的第一节点相遇，于是就找到了入环第一个节点。
方法二：
我们可以在相遇点处将链表切断，然后经过反转链表的到'Y'型，于是乎这题就转变为了题型三的类型，即相交链表找第一个相交节点，如下所示：
有两点需要注意：
- 如图中1处，我们是将
L + X的部分反转； - 如图中2处，最后需要将指向原头位置的指针指向
NULL。
LeetCode链接: 142. 环形链表 II
解题代码
//基于方法一的解法： struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow = head, *fast = head; //判断fast和slow相遇的地方 while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(fast == slow) break; } if(fast == NULL || fast -> next == NULL) return NULL; struct ListNode* meet = slow; //2(L+X) = L+nC+X //L+X=nC(C为环长，L为环外面部分长,X为进环点到相遇点的距离) while(meet != head) { meet = meet->next; head = head->next; } return meet; }
