题目描述
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
解题思路
第一步,找环中相汇点。分别用p1,p2指向链表头部,p1每次走一步,p2每次走二步,直到p1==p2找到在环中的相汇点。
第二步,找环的入口。接上步,当p1==p2时,p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x; n=x;可以看出p1实际走了一个环的步数,再让p2指向链表头部,p1位置不变,p1,p2每次走一步直到p1==p2; 此时p1指向环的入口。
代码如下
public ListNode EntryNodeOfLoop(ListNode pHead)
{
ListNode listNode1=pHead;
ListNode listNode2=pHead;
try {
int flag=0;
while (pHead.next!=null) {
if (listNode1==pHead) {
flag++;
if (flag>=2) {
return null;
}
}
listNode1=listNode1.next;
listNode2=listNode2.next.next;
if (listNode1==listNode2) {
listNode2=pHead;
while(listNode1!=listNode2)
{
listNode1=listNode1.next;
listNode2=listNode2.next;
}
if (listNode1==listNode2) {
return listNode1;
}
return listNode1;
}
}
} catch (NullPointerException e) {
return null;
}
return null;
}
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
版权声明:本文为weixin_42007892原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。