给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
思路:
1.判断链表中有环 -> 2.得到环中节点的数目 -> 3.找到环中的入口节点
public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { if(pHead == null) return null; ListNode l = pHead, f = pHead; boolean flag = false; while(f != null && f.next != null){ l = l.next; f = f.next.next; if(l == f){ flag = true; break; } } if(!flag){ return null; }else{ int n = 1; f = f.next; while(l != f){ f = f.next; n++; } l = f = pHead; for(int i = 0; i < n; i++){ f = f.next; } while(l != f){ l = l.next; f = f.next; } return l; } } }方法二 环前面的路程 = 数个环的长度(为可能为0) + c - a c - a为相遇后剩下的路程 1.找到相遇点 -> 2.新建指针从头结点开始走,慢结点也开始走,相遇则是入口节点。
public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { if(pHead == null && 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){ ListNode slow2 = pHead; while(slow2 != slow){ slow2 = slow2.next; slow = slow.next; } return slow2; } } return null; } }