题解 | #链表中环的入口结点#

链表中环的入口结点

http://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4

这道题告诉我两件事情,一是一些题没有数学思维就不好办,不会就记下来(比如根据相遇点和起始点找环入口点);二是别乱加逻辑(见下面的代码)。

(已通过)
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead == null) return null;
        if(pHead.next == pHead) return pHead;
        if(pHead.next == null) return null;
        ListNode fast = pHead;
        ListNode slow = pHead;
        while(fast != null && fast.next != null){
            // 这里不要乱加逻辑
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)
                break;
        }
        if(fast == null || fast.next == null) return null;
        while(pHead != fast){
            pHead = pHead.next;
            fast = fast.next;
        }
        return pHead;
    }
}

而一开始我的逻辑是这样的:

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead == null) return null;
        if(pHead.next == pHead) return pHead;
        if(pHead.next == null) return null;
        ListNode fast = pHead; // 1
        ListNode slow = pHead; // 2
        while(fast != null && fast.next != null){
            if(fast != slow){ // 3
                fast = fast.next.next;
                slow = slow.next;
            }
            else{
                break;
            }
        }
        if(fast == null || fast.next == null) return null;
        while(pHead != fast){
            pHead = pHead.next;
            fast = fast.next;
        }
        return pHead;
    }
}

上面的代码问题在于 1 和 2 表明快慢指针一开始处于同一个位置,导致 3 处的循环一开始就没进去过,直接导致 break 退出循环,所以值永远是第一个节点。
如果快慢指针起始位置改成不一样呢?能行吗?

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead == null) return null;
        if(pHead.next == pHead) return pHead;
        if(pHead.next == null) return null;
        ListNode fast = pHead.next;
        ListNode slow = pHead;
        while(fast != null && fast.next != null){
            if(fast != slow){ // 1
                fast = fast.next.next;
                slow = slow.next;
            }
            else{
                break;
            }
        }
        if(fast == null || fast.next == null) return null;
        while(pHead != fast){
            pHead = pHead.next;
            fast = fast.next;
        }
        return pHead;
    }
}

答案是不行,会死循环,因为快慢指针一般都是指向同一个节点,这样才能保证后面每次快指针都比慢指针稳定拉开 1 步距离。而如果一开始快指针就在慢指针前面,就会导致两者相差 2,会造成快指针刚好错开相遇点(起始距离是 2,相当于走了两步),永远也无法跟慢指针相遇(哪怕循环里没乱加逻辑)。

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 17:58
点赞 评论 收藏
分享
Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司9个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务