【数据结构】链表经典OJ题，常见几类题型（二）
【数据结构】链表经典OJ题，常见几类题型（二）
题型三：链表相交，找相交节点
思路解析
看到这类题型首先要判断链表是否相交，而相交条件：两链尾部节点相同（地址相同，
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。
OJ实例
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;
}