题解 | #链表中环的入口结点#
链表中环的入口结点
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,相当于走了两步),永远也无法跟慢指针相遇(哪怕循环里没乱加逻辑)。