链表中环的入口结点

发表于 | 分类于 ，

题目描述

一个链表中包含环，请找出该链表的环的入口结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/*
 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 || pHead.next == null){
           return null;
       }
        ListNode node1 = pHead;
        ListNode node2 = pHead;
        while(node2 != null){
            node1 = node1.next;
            node2 = node2.next.next;
            if(node1 == node2){
                break;
            }
        }
        node1 = pHead;
        while(node1 != node2){
            node1 = node1.next;
            node2 = node2.next;
        }
        return node1;
    }
}