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

链表中环的入口结点

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,相当于走了两步),永远也无法跟慢指针相遇(哪怕循环里没乱加逻辑)。

全部评论

相关推荐

点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务