5.1.54 54.链表中环的入口结点
优质
小牛编辑
127浏览
2023-12-01
一、题目
一个链表中包含环,如何找出环的入口结点?
二、解题思路
可以用两个指针来解决这个问题。先定义两个指针P1和P2指向链表的头结点。如果链表中环有n个结点,指针P1在链表上向前移动n步,然后两个指针以相同的速度向前移动。当第二个指针指向环的入口结点时,第一个指针已经围绕着环走了一圈又回到了入口结点。
剩下的问题就是如何得到环中结点的数目。我们在面试题15的第二个相关题目时用到了一快一慢的两个指针。如果两个指针相遇,表明链表中存在环。两个指针相遇的结点一定是在环中。可以从这个结点出发,一边继续向前移动一边计数,当再次回到这个结点时就可以得到环中结点数了。
三、解题代码
public class Test {
private static class ListNode {
private int val;
private ListNode next;
public ListNode() {
}
public ListNode(int val) {
this.val = val;
}
@Override
public String toString() {
return val +"";
}
}
public static ListNode meetingNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
// 链表中没有环
if (fast == null || fast.next == null) {
return null;
}
return fast;
}
public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode meetingNode=meetingNode(pHead);
if(meetingNode==null)
return null;
// 得到环中的节点个数
int nodesInLoop=1;
ListNode p1=meetingNode;
while(p1.next!=meetingNode){
p1=p1.next;
++nodesInLoop;
}
// 移动p1
p1=pHead;
for(int i=0;i<nodesInLoop;i++){
p1=p1.next;
}
// 移动p1,p2
ListNode p2=pHead;
while(p1!=p2){
p1=p1.next;
p2=p2.next;
}
return p1;
}
}