判断链表中是否有环及链表开始入环的第一个节点

两个题目的oj链接如下：

给定一个链表，判断链表中是否有环：

https://leetcode-cn.com/problems/linked-list-cycle/description/

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

https://leetcode-cn.com/problems/linked-list-cycle-ii/description/

（1）给定一个链表，判断链表中是否有环：

我们可以用快慢指针的方法解决这个问题。fast指针一次走2步，slow指针一次走1步，则当两个指针走一次时两个指针相差1步，走两次时相差2步，以此类推当走n次时fast指针与slow指针相差n步，每多走一次两个指针之间相差步数加1。

若slow走n步入环，则此时fast以入环且比slow快n步，因为在环中，故我们可以看作fast指针在追赶slow指针，设环长为L，则fast与slow相差L-n步。已知每多走一次两个指针之间相差步数加1，则当fast追slow时，每多走一次两个指针之间相差步数减1。因此fast与slow相差步数从L-n一直递减至0，此时两指针相遇。

因此当两指针相遇时我们可以说链表有环。

（若fast走其他大于2的步数，则当fast追slow时步数差减少有可能会错过0步，直接超过slow，当环数处于一个特殊值时两个指针可能永远不会相遇，每次将要相遇时fast将会直接超过slow）

判断链表中是否有环及链表开始入环的第一个节点

（直线为入环前的链表，环可以为任意非0数的结点，此处仅以5做表示）

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

（2）给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null：

算法：

与前一题相同，先找到fast与slow指针相遇的结点，然后维护两个指针fast指针以一次1步的行动方式从相遇结点开始行动，slow指针以相同行动方式从链表的第一个结点开始行动，当两指针相遇时相遇结点便是入环的第一个结点。

算法分析：

判断链表中是否有环及链表开始入环的第一个节点

设meet结点与入环第一个结点相差f，当两指针在meet结点相遇时，slow走过的距离为n+f，fast走过的距离为n+f+xL（x为未知次，因为若环较小时当slow入环时fast已经遍历环若干次了）fast走过的距离为slow的二倍

判断链表中是否有环及链表开始入环的第一个节点

当fast从meet结点开始行动时，剩下的距离就为L-f了，而slow从链表的第一个结点开始走时剩下的距离为n，因此当两指针相遇时相遇结点变为入环的第一个结点。（因为x为遍历环的次数，无论遍历多少次环都会回到相同的结点，所以x可以忽略）

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

    if (fast == NULL || slow == NULL || fast->next == NULL){
        return NULL;
    }
    
    fast = head;
    
    while (fast != slow){
        fast = fast->next;
        slow = slow->next;
    }
    
    return fast;
}

判断链表中是否有环及链表开始入环的第一个节点

相关推荐