【数据结构】链表经典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;
}