美文网首页
算法-23.链表中环的入口结点

算法-23.链表中环的入口结点

作者: zzq_nene | 来源:发表于2020-08-19 15:11 被阅读0次
一个链表中包含环,请找出该链表的环的入口节点。要求不能使用额外的空间。

思路:定义一个链表,从头结点开始执行,定义头节点到入口节点的距离为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;
    }

相关文章

  • 算法-23.链表中环的入口结点

    一个链表中包含环,请找出该链表的环的入口节点。要求不能使用额外的空间。 思路:定义一个链表,从头结点开始执行,定义...

  • 剑指offer.C++.code56-60

    56. 链表中环的入口结点 一个链表中包含环,请找出该链表的环的入口结点。 57. 删除链表中重复的结点【基于递归...

  • 链表

    合并排序链表 链表排序 链表中环的入口结点 给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出nul...

  • [剑指offer] 链表

    链表中环的入口结点 题目描述给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。 解题思路:...

  • JZ-055-链表中环的入口结点

    链表中环的入口结点 题目描述 给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。题目链接:...

  • 链表-链表中环的入口结点-java/c++

    链表中环的入口结点 题目描述 一个链表中包含环,请找出该链表的环的入口结点。 思路一: 用map或者set,遍历链...

  • 【链表】链表中环的入口结点

  • 链表中环的入口结点

    题目描述:给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。 思路:a、第一步,找环中相汇...

  • 链表中环的入口结点

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

  • 链表中环的入口结点

    快慢指针f , s,两指针相遇时,f = 2* s, 设环长度为n,n = s再一个慢指针从链表头开始,两个慢指针...

网友评论

      本文标题:算法-23.链表中环的入口结点

      本文链接:https://www.haomeiwen.com/subject/mzxbdktx.html