leetcode c++做题思路和题解（2）——链表的例题和总结

链表的例题和总结

0. 目录

环形链表

1. 环形链表

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

看了别人的思路真是感概万千，思路这个东西啊，哈哈哈

官方方法1: 哈希表
官方方法2: 快慢指针
奇葩方法1: 标记访问过的节点(会破坏链表)
奇葩方法2: 倒因为果法

1.1 哈希表

略

1.2 快慢指针

思路就是田径场的追击问题, 如果有环, 那么跑得快的一定会碰到跑的慢的.

跑得快的一次走两步, 跑得慢的走一步.

fast=fast->next->next;
slow=slow->next;

1.2.1 代码

bool hasCycle(struct ListNode *head) {
    if((head==NULL)||(head->next==NULL)) return false;
    if(head->next->next == head) return true;
    struct ListNode *fast = head;
    struct ListNode* slow = head;
    while((fast != NULL)&&(fast->next != NULL)){
        fast = fast->next->next;
        slow = slow->next;
        if(fast==slow) return true; //碰到了
    }
    return false;
}

1.2.2 关于快慢指针的差值设置

其实一直在想快指针能不能更激进些, 例如一次走三步, 这样就会更快了, 于是有了以下的思考. 结论是:

快慢指针的差值不能随意设置, 否则可能有环也检测不出来, 见举反例证明
差值的设置与环形的节点数有关, 而这个我们无法获取(苦笑), 所以最好就是差值为1吧

定义

真相遇：离散的情况下，只有快慢指针到同一位置才算真相遇
假相遇：离散的情况下，快指针超越了慢指针，但没真相遇（在连续情况下就两者肯定就算相遇了）,例如快由1到了3,慢由1到2的情况就是假相遇.

举反例证明快指针确实不能随意设置

假设环内节点为n，快指针速度为n+1，慢指针速度为1。假设某时刻快指针比慢指针先到环，慢指针刚到环起点0，快指针在n-1（在慢指针后一个位置），这样快指针将永远在慢指针后面一个节点上。

差值的设置

以下是大佬ljjtyjr的评论

关于快慢指针中两个指针的速度问题：和龟兔赛跑问题不同的是，龟兔赛跑是一个连续性的问题，无论二者的速度差是多少，可以这样假设：假设赛道长度为s，v_f表示速度快的值，v_s表示速度慢的值，（假设二者初始位置相同），那么可以求出来：(v_f-v_s)t=s；这样求出来的t，是二者第一次相遇的时间；本题不同的是：对于链表来说是一个离散的值，我们假设环内共有n个节点，同样假设快指针与慢指针分别是v_f，v_s；如果想要相遇（假设初始位置相同），同样有(v_f-v_s)k = n； ——这个时候 v_f，v_s 为正整数，k为循环次数，n为节点数目； k = n/(v_f-v_s）如果想要k为整数，那么可以看到二者的速度差是有要求的，必须能够被n整除；注意：这样求得是第一次相遇，也有可能v_f-v_s是n的整数倍；

正是由于离散的存在假相遇, 所以(v_f-v_s)k = n这个式子就有问题了, 应该改成(v_f-v_s)k = ln, 其中l表示快指针套了多少圈. 这个(v_f-v_s)k = n,感觉是不是没有考虑到假相遇的情况.

1.3 奇葩方法1 标记访问过的节点

此类方法的思路就是沿路标记访问过的节点, 如果后续遇到节点有我们的标记, 则表明有环. (方法缺点是会破坏链表, 但我很喜欢这类思路)

关于标记的方法, 不同语言可能不一样, 这里按照思路分为两种:

标记val变量
标记节点本身的指针

以下举两个大神的例子, 其他语言思路应该差不多.

1.3.1 python版标记val变量

以下代码摘自大神全村人的希望

思路设置val为'bjfuvth'(这个应该是随便取的), 如果后续某节点val也为'bjfuvth', 则有环. 但是需要确保原列表中没有这个值.

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        while head:
            if head.val == 'bjfuvth':
                return True
            else:
                head.val = 'bjfuvth'
            head = head.next
        return False

1.3.2 C和C++版标记节点本身的指针

以下代码和思路摘自大神JIANcoder

这个方法比val方法我感觉要好点, 因为新建的END的指针可以确保和原链表中的不重复.

 //新建END节点，将遍历过的节点指向END，如果==END就是有环
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head) return false;
        ListNode * END =new ListNode(0);
        ListNode* pre;
        while(head){
            if(head==END) return true;
            pre=head;
            head=head->next;
            pre->next=END;
        }
        return false;
    }
};

1.4 奇葩方法2: 倒因为果法

这是大神恶搞大王的专属坑位. 逻辑之奇葩, 思路之搞笑.

思路就是: 直接遍历访问链表, 并且计数, 如果计数过大, 则说明有环.(问题就在节点数不能预知上, 但是思路还是可以的)

以下摘自大神恶搞大王:

bool hasCycle(struct ListNode *head) {
    if(head){
        int times = 0;
        struct ListNode *root = head;
        while(root->next){
            root = root->next;
            times++;
            if(times>10000){ //如果节点数大于10000, 这个方法就不可行了
                return true;
            }
        }
    }
    return false;
}