一个链表中包含环,请找出该链表的环的入口节点。要求不能使用额外的空间。
思路:定义一个链表,从头结点开始执行,定义头节点到入口节点的距离为x,然后采用双指针的方式,一个fast指针每次移动两个节点,一个slow指针每次移动一个节点,然后查找两个节点是否最终会相等,如果相等表示存在相遇点,那么说明存在圆环。
上面已经定义入口节点到头节点的距离为x,然后定义相遇节点为p,入口节点为q,则定义q->p的距离为y,p->q的距离为z,做公式运算:
fast指针移动的距离:x+y+z+y
slow指针移动的距离:x+y
又因为fast每次移动两个节点,slow指针每次移动一个节点,则x+2y+z=2(x+y)
最终,x=z
说明从相遇节点p到入口节点的距离,是等于从头节点到入口节点的距离
所以要先找到相遇节点,然后再从头节点开始进行遍历,同时遍历相遇节点,每次移动一个节点的位置,当最终两个移动结果发生相等之后,则相等的节点就是入口节点
public ListNode EntryNodeOfLoop(ListNode pHead) {
if (pHead == null || pHead.next == null)
return null;
ListNode slow = pHead, fast = pHead;
do {
fast = fast.next.next;
slow = slow.next;
} while (slow != fast);
fast = pHead;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
网友评论