链表中环的入口结点

编程练习

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

思路：首先想到了带环的链表的特性就是形成环的两个节点的关系是环尾节点的next指向环头结点。也就是说环尾结点的next指向的是之前已经遍历过得结点，这样就会形成环。

　　主要思想掌握了，接下来编程就很简单了，我们想到需要引入一个盛装listnode的容器以便后续的遍历判断，很容易想到Arraylist。注意：用Aarraylist盛装带环的链表时需要考虑如何避免陷入死循环，给循环设立出口。

java代码如下：

import java.util.ArrayList;
public class EntryNodeOfLoop {
	
    public static ListNode EntryNodeOfLoop(ListNode pHead){
    	ArrayList<ListNode> list=new ArrayList<ListNode>();
        //注意，要装入一个带环的链表，需要给循环设置跳出，不然会陷入死循环。
    	while(pHead!=null) {
        	list.add(pHead);
        	if(list.contains(pHead.next)) {
        		break;
        	}else {
        		pHead=pHead.next;
        	}
        }
        for(int i=0;i<list.size();i++) {
        	for(int j=i;j>=0;j--) {
        		if(list.get(i).next==list.get(j)) {
        			return list.get(j);
        		}
        	}
        }
    	
    	return null;
    }
    public static void main(String[] args) {
    	ListNode l1=new ListNode(1);
		ListNode l2=new ListNode(2);
		ListNode l3=new ListNode(3);
		
		l1.next=l2;
		l2.next=l3;
		l3.next=l1;
		
		System.out.println(EntryNodeOfLoop(l1).val);
	}
	
}