2015-08-16

LeetCode | 链表相关算法总结

这里总结一下常见的与链表有关的算法。

链表成环的各种问题

判断一个单链表是否存在环

这个思路比较简单，用 两个指针代表快、慢指针，然后从头指针开始，快指针一次前进两个结点，慢指针一次前进一个结点，则如果两个指针相遇（相等），则一定有环。若两指针不相遇，则 fast 指针遇到空指针后便结束循环。

扩展：这种快、慢指针的思路还可用于找到无环链表的中间元素，当快指针到尾部时，慢指针正好到中间元素的位置。可用于链表的归并排序。
扩展：这种两个指针的思路还可以用于寻找链表的第k个结点，思路同上。

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

若存在环，求环的长度

此处有定理I： 两指针（fast和slow）从第一次碰撞点出发到第二次碰撞所走的长度即为环的长度。

链表成环的情况

若存在环，求环的入口（连接点）

此处有定理II：第一次碰撞点到环的入口的距离，等于头指针到环的入口的距离。因此，分别从头指针和碰撞点遍历链表，第一次相遇的点即为换的入口（连接点）。

证明如下：
设单链表的总长度为L，头结点到环入口的距离为a，环入口到快慢指针相遇的结点距离为x，环的长度为r，慢指针总共走了s步，则快指针走了2s步。并且，快指针要追赶上慢指针，在环内的圈数n >= 1；因此我们可以列出式子：

$$s = a + x$$
$$2s = a + nr + x$$
$$=> a = nr - x = (n-1)r + y$$

由上式可知成立。
对应：LeetCode 142 - Linked List Cycle II

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) {
                ListNode *q = head;
                while(q != slow) {
                    q = q->next;
                    slow = slow->next;
                }
                return q;
            }
        }
        return nullptr;
    }
};

链表相交的各种问题

如何判断链表相交，若相交则找到第一个交点

Question：给出两个单向链表的头指针，而两个链表都可能带环，判断这两个链表是否相交，并且给出他们相交的第一个节点。

思路：

首先根据上边的算法判断链表是否成环。

第一种情况：两个链表都不成环
思路1：将其中一个链表首尾相连，判断另一个链表是否存在环，如果存在，则两个链表相交，且找出来的环入口点即为相交的第一个点。
思路2：若如果两个不成环的链表相交，那么两个链表从相交点到尾结点都是相同的结点。首先先遍历两个链表，记录下两个链表的长度（长链表a，短链表b）。然后先让长链表移动a-b长度，然后两链表开始同步前进，相遇的第一个点即为环的第一个交点。

    A:          a1 → a2
                       ↘
                         c1 → c2 → c3
                       ↗            
    B:     b1 → b2 → b3

对应：LeetCode 160 - Intersection of Two Linked Lists

第二种情况：两个链表都成环

不可能的情况：一个有环，一个没有环

很好想的，如果两个链表一个有环，一个无环的话，那么它们不可能相交。

本文标题:LeetCode | 链表相关算法总结

文章作者:sczyh30

发布时间:2015年08月16日

原始链接:http://www.sczyh30.com/posts/Algorithm/algorithm-linkedlist-leetcode/

许可协议: "知识共享-保持署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。