链表算法题（下）

标签：slow ListNode fast 链表算法节点指针

在链表算法题（上）长中我们已经学习了一系列的链表算法题，那么在本篇中我们将继续来学习链表的算法题，接下来就继续来破解链表的算法题吧！

1.相交链表

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

通过以上的题目的描述该算法题要我们实现的代码功能是判断两条链表是否相交，如果相较的话就返回相较节点的指针，不相较就返回NULL

那么在实现该算法题的代码之前先要来分析如何实现判断是否是相交链表

首先来看相交链表有什么特征呢？来看以下的示例

从以上的示例就可以看出当两个链表是相交的，那么在这两条链表内一定会有两个节点的下一个节点是相同的。而如果链表不是相交的，那么就不会有两个节点的下一个节点是相同的

当两个链表是相较的时候我们需要返回的就是以上这个节点，那么该如何来找出这个相交的节点呢？

在此我们的解决方法是先定义两个指针变量一开始分别指向两个链表的第一个节点，之后通过各遍历一次两条链表，之后就得到这两条链表各自的节点个数，之后将得到的两个节点数大的减小的得到两链表长度的差值，将节点个数多的链表的定义的节点指针往后走之前得到的差值，最后将两个链表的指针同时往后遍历，当两个指针相同时就说明这两个链表为相交链表，否则就不相交

例如以下示例：

首先A链表个数为5，B节点个数为6，两个链表节点差值就为1

在定义两个指向两个；链表的第一个节点的指针pcur1和pcur2，由于B链表为节点个数多的链表因此将B链表的指针pcur2先向后走1步

之后让pcur1和pcur2同时向后遍历，之后pcur1和pcur2同时指向c1节点，这就可以说明A和B这两个链表是相交链表

接下来我们就来实现该算法题的代码
在以下得到两个链表的节点数差值使用的是库函数abs，该函数能计算出差值的绝对值

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    ListNode* pcur1=headA;
    ListNode *pcur2=headB;
    
    int count1=0;
    int count2=0;
    while(pcur1)//得到第一个链表的结点数
    {
        count1++;
        pcur1=pcur1->next;
    }
    while(pcur2)//得到第二个链表的节点数
    {
        count2++;
        pcur2=pcur2->next;
    }
    int tmp=abs(count1-count2);//得到两个链表节点数的差值
    ListNode* longlist=headA;
    ListNode* shortlist=headB;
    if(count1<count2)//确定长短链表
    {
        longlist=headB;
        shortlist=headA;
    }
    while(tmp--)//先将长链表走tmp步
    {
        longlist=longlist->next;
    }
    while(longlist && shortlist)//同时遍历两个链表
    {
        if(longlist==shortlist)
        {
            return longlist;
        }
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return NULL;
}

2.环形链表I

141. 环形链表 - 力扣（LeetCode）

根据以上的题目描述就可以看出该算法题要我们实现的是判断链表是否为循环链表，在此循环链表是指链表的尾节点不在是连接NULL，而是连接链表中的其中一个节点

那么使用什么方法能判断链表是否为循环链表呢？

在此我们使用的是之前学习过的前后指针法，首先定义有两个指针变量fast和slow，之后fast指针每次走两步，slow指针每次走一步，到最后如果fast指针和slow相遇就说明该链表为循环链表

例如以下示例：

要判断以上链表是否为循环链表我们来看看使用前后指针法的过程是什么样的，首先定义快指针fast和满指针slow，之后让fast和slow遍历链表

正如上图所示slow指针和fast指针在节点-4相遇，这就说明该链表为循环链表为循环链表

接下来我们就来实现该算法题的代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) 
{
    ListNode* fast,*slow;
    fast=slow=head;
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            return true;
        }
    }
    return false;
}

在解决了以上的算法题后我们就要思考为什么快指针每次走两步，慢指针走一步可以相遇，有没有可能遇不上呢？

slow一次走⼀步，fast一次走2步，fast先进环，假设slow也走完入环前的距离，准备进环，此时fast和slow之间的距离为N，接下来的追逐过程中，每追击⼀次，他们之间的距离缩小1步

这时在追击过程中fast和slow之间的距离变化：

因此，在带环链表中慢指针走一步，快指针走两步最终一定会相遇。

那么在解决以上问题后思考快指针一次走3步，走4步，...n步行吗?

step1:
按照上面的分析，慢指针每次走一步，快指针每次走三步，此时快慢指针的最大距离为N，接下来的追逐过程中，每追击一次，他们之间的距离缩小2步
追击过程中fast和slow之间的距离变化：

分析:
1、如果N是偶数，第一轮就追上了
2、如果N是奇数，第一轮追不上，快追上，错过了，距离变成-1，即C-1，进入新的一轮追击
a：C-1如果是偶数，C-1如果是偶数，那么下一轮就追上了
b：C-1如果是奇数，那么就永远都追不上
总结一下追不上的前提条件：N是奇数，C是偶数

step2：

在以上的step1中我们得出当fast追不上的前提条件：N是奇数，C是偶数，那么接下来我们就要继续分析这种情况是否会出现

假设：
环的周长为C，头结点到slow结点的长度为L，slow走一步，fast走三步，当slow指针入环后，slow和fast指针在环中开始进行追逐，假设此时fast指针已经绕环x周。
在追逐过程中，快慢指针相遇时所走的路径长度:

$fast: L+xC+C-N$
$slow: L$

由于慢指针走一步，快指针要走三步，因此得出： 3 * 慢指针路程 = 快指针路程 ，即：

$3L=L+xC+C-N$
$2L=(x-1)C-N$

对上述公式继续分析：由于偶数乘以任何数都为偶数，因此 2L 一定为偶数，则可推导出可能得情
况：
• 情况1：偶数 = 偶数 - 偶数
• 情况2：偶数 = 奇数 - 奇数

由step1中（1）得出的结论，如果N是偶数，则第一圈快慢指针就相遇了。
由step1中（2）得出的结论，如果N是奇数，则fast指针和slow指针在第一轮的时候套圈了，开始进行下一轮的追逐；当N是奇数，要满足以上的公式，则 (x+1)C 必须也要为奇数，即C为奇数，满足（2）a中的结论，则快慢指针会相遇

因此， step1 中的 N是奇数，C是偶数不成立，既然不存在该情况，则快指针一次走3步最终一定也可以相遇。

因此快指针一次走4、5.....步最终也会相遇，其证明方式同上

注：虽然已经证明了快指针不论走多少步都可以满足在带环链表中相遇，但是在编写代码的时候会有额外的步骤引入，涉及到快慢指针的算法题中通常习惯使用慢指针走⼀步快指针走两步的方式。

3.环形链表II

142. 环形链表 II - 力扣（LeetCode）

在以上环形链表I中我们已经实现了如何判断一个链表是否为环形链表，接下来我们在环形链表算法题中我们将跟进一步当链表是环形链表时我们还要返回链表进入环的第一个节点

那么要如何才能找到环形链表进入环的第一个节点呢？接下来我们要来了解一个性质

让一个指针从链表起始位置开始遍历链表,同时让⼀个指针从判环时相遇点的位置开始绕环运
行,两个指针都是每次均走一步,最终肯定会在入口点的位置相遇。

例如以下示例：

根据使用快慢指针法我们就可以的到以上链表两指针的相遇节点为-4

在此之后我们再定义一个指针变量pcur指向链表的第一个节点，之后让pcur指针和fast指针同时遍历，当这两个指针指向同一个节点时，指针指向的节点就是入环前的节点

接下来我们就来实现该算法题的代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head)
{
    ListNode* fast,*slow;
    fast=slow=head;
    while(fast&& fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        {
            ListNode* pcur=head;
            while(pcur!=fast)
            {
                pcur=pcur->next;
                fast=fast->next;
            }
            return fast;
        }
    }
    return NULL;
}

在解决了以上的算法题后我们就要证明为什么在环形链表中以上的这种性质：