数据结构每日亿题(三)

一.环形链表

原题传送门：力扣

题目：

这一题的目的是让你判断一下一个链表是否有环。

现在有一个指针，假设这个链表带环，这个指针如果一直向后走，它的运动轨迹是不是先走到环的节点那里，然后一直在环里循环。如果这是没环的链表，那指针指针一直走，直到为空则停止。

现在我们在定义一个指针，这个指针走的比刚才那个指针慢，而且是慢一倍。也就是这里有个快指针一次走两步，有个满指针，一次走一步：

我们抽象一点，将这个链表画成这个样子。接下来我们慢慢移动这两个指针：

现在快指针即将进入环里面了，慢指针走的路程是快指针走的一半，然后我们继续走：
当慢指针也走到这个节点时，我们假设fast走到图中指向的那个位置上，此时这个快指针是走了好几圈还是第一圈，我们也不清楚，反正就先假设走到这里。

好，到目前为止，我们定义的两个指针都已经进入了环里面了，我们现在假设他们之间距离为N：
因为我们刚才已经设置好了，快指针一次走两步，慢指针一次走一步，这也就意味着，两个指针每走一次，他们之间的距离都会-1，而总距离是N。N,N-1,N-2,N-3…这样总会有一步导致它们俩相遇，只要相遇就知道这个链表带环。

如果链表不带环，因为快指针走的快，所以肯定会提前到达结尾，这时候我们要分两种情况：

如果链表节点个数为偶数个，fast总共要走两次，走到NULL，停下来。

如果个数是奇数个，fast->next要为空才能停下来。

所以我们的循环条件可以这样写：

    struct ListNode* fast = head;
    struct ListNode* slow = head;

    while(fast && fast->next)
    {
    	...
    }
1
2
3
4
5
6
7

这样写的目的是，可以让两个指针在循环体内部运动，如果这个链表没有环，就一定能跳出循环，如果含有环，循环就会一直走，直到两个指针相遇，相遇后就直接返回，也不需要跳出循环了。

/**
 * 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 && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这里还要考虑链表为空的情况，如果为空就直接跳过循环返回false.

现在还有一个问题，快指针一定要比慢指针多走一步吗？多走2步，3步可不可以呢？
首先假设快慢两个指针进环之后的距离是N，如果快指针每次多走两步，它们之间的距离就是：
N
N-2
N-4
…
但我们也不清楚N是奇数还是偶数，如果是偶数那恭喜你，同样可以做出来，但如果是奇数呢？
N-6
N-8
…
1
-1
这样的话距离就变成-1了，也就是说，快指针超过了慢指针而且多跑了一步：

这也就意味着，它们之间的距离从N变成了圈大小-1，我们假设圈长度是C，所以距离从N变成了C-1。但是我们还有一次机会，如果C-1是偶数的时候，我们依然能赶上，但相同道理，我们不知道环的大小，所以依然判断不了其是奇是偶。如果运气不好C-1是奇数，每次距离-2，到最后它们的距离还是变成了C-1.

同理快指针多走3步，4步…都是一个道理。所以说最稳健，最合理的就是快指针一次走2步，慢指针一次走一步。

二.环形链表 II

2.1

原题传送门：力扣

题目：

这题和第一题差不多，只是这题多了一个条件：让你返回入口节点。

刚才那一题我们只是判断了链表是否带环，但是没有判断链表环的入口在哪，也就是找这个地方：

我们假设第一题定义的快慢两个指针是在这里相遇的：

现在我们肯定很难想到比较好的解决方法，所以我们还是从数学的角度来寻找结果，我们通过刚才两个指针走的路程来找下面这三段的关系：

慢指针走的路程应该是L+(N)这一段，因为它不会像快指针那样在环里绕几圈，慢指针只可能走一圈的一部分。

那快指针走的路程呢？它们两个指针走的时间是一样的，而速度是两倍的关系，所以说快指针走的路程是慢指针的两倍。而快指针走的路程我们也可以直到L+(N*k)+(N)这里乘一个k是因为我们不知道快指针实际在里面转了多少圈，所以最后表达式是：

(L+N)2 = L+CK+N

两边约一下：

L = C*k - N

但是仔细想一下，这个k是不是对我们的算式没什么用处啊，C-N,2C-N,3C-N所在的地方是不是一样的？

也就是说L和C-N这两个距离相等：
所以现在思路就有了，我们在定义两个指针cur指向头节点，meet指向之前两个指针相遇的节点：
然后让这两个指针同时且步长相同的往后走，然后它们相遇的节点是不是就是我们需要求的节点？

把第一题的代码稍作改进即可：

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            struct ListNode* meet = fast;
            struct ListNode* cur = head;
            while (meet != cur)
            {
                meet = meet->next;
                cur = cur->next;
            }
            return meet;
        }
    }
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.2

这一题我再来将一种方法：
我们先将第一题找到的那个相遇的节点与下一个节点断开：

这样我们就把一个链表，变成了两个链表：

两个链表一个从头开始走，一个从meet指向的节点后面开始走，最终都走到meet指向的节点那里停下来。现在我们是不是把找路口的问题变成了找两个链表交点的问题？
关于相交链表的为题我在每日亿题(二)的最后一题里提到过，这里我就不再赘述，现在我们直接将那个函数拿来用。

//返回两个链表的相交节点
 struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    int lenA = 0;
    int lenB = 0;

    //随便定义两个指针，因为此时还不知道哪个长哪个短
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;

    //计算链表的大小
    while (curA->next)
    {
        curA = curA->next;
        lenA++;
    }
    while (curB->next)
    {
        curB = curB->next;
        lenB++;
    }

    //此时curA,curB指向链表末尾，如果两者地址不相等说明没有交点
    if (curA != curB)
        return NULL;

    //计算两个数差值的绝对值，也就是快指针该走的步数
    int absoulte = abs(lenA - lenB);

    //随便定义两个指针，因为此时还不知道哪个长哪个短
    struct ListNode* fast = headA;
    struct ListNode* slow = headB;

    //假设headA比headB要长，如果猜错了就换一下位置
    if (lenA < lenB)
    {
        fast = headB;
        slow = headA;
    }

    //此时将快指针先走absoulte步
    while (absoulte--)
    {
        fast = fast->next;
    }

    //遍历
    while (fast != slow)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            struct ListNode* meet = fast;
            struct ListNode* next = meet->next;
            //保存相遇节点后一个位置将相遇处的节点断开
            meet->next = NULL;

            struct ListNode* cur = head;

            return getIntersectionNode(next,cur);
        }
    }
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

虽然这种写法很容易想到，但是代码要写的太多了