链表中环的入口结点 代码 思路 坑 知识点 More

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

代码

1
2
3
4
5
6
7
8
9
10

public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.ArrayList;
public class {

public ListNode EntryNodeOfLoop(ListNode pHead)
{
ArrayList<ListNode> list = new ArrayList<ListNode>();
if(pHead == null) return null;
while(!list.contains(pHead)){
list.add(pHead);
pHead = pHead.next;
if(pHead == null) return null;
}
return pHead;
}
}

思路

遍历一遍链表,并将每个节点存入ArrayList,如果遍历过程中发现ArrayList已经存在当前节点,那说明这个就是我们要找的节点

1 题目说是链表有环,但是提交代码后,发现要判断这个链表有没有环。

知识点

1 了解下ArrayList的contain方法是怎么实现的

More

看别人提交的代码,像是在解一道数学题,首先你要设x=2y,然后回推,效率是高的,复杂度也低,但是耗脑子,可以学习一波。