链表中环的入口节点

qpal 发布于2019-08-16 18:28 / 568人阅读

摘要：题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出。

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead){
        
    }
}

解法一

遍历链表的时候，用一个容器list依次装入链表的节点，如果发现有重复的节点，那么就是链表的环的入口节点

import java.util.ArrayList;
public class Solution {

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

        return pHead;
    }
}

时间复杂度：O(n^2)

解法二

采用双指针的方法（这个方法还可以用来判断链表中有没有环），一个快指针一个慢指针，快指针一次走两步，慢指针一次走一步，如果链表中有环，那么两个指针一定就可以相遇，并且相遇的地方，一定在环的某处

设相遇的地方距环的入口点一边有a个节点，一边有b个节点，链表除环以外有x个节点，环中一共有c个节点（c=a+b）

那么可以得到如下关系式，用b = c -a表示

][1]

 public ListNode EntryNodeOfLoop(ListNode pHead){
        if(pHead == null || pHead.next == null)return  null;
        ListNode slow = pHead.next;
        ListNode fast = pHead.next.next;
        while (slow != fast && pHead != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        slow = pHead;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

该方法的时间复杂度为O(n)

参考

《剑指offer》——链表中环的入口结点

海外云主机服务器托管 c语言链表加节点中环 linux链表的安全访问小程序的入口

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/75158.html

写一段代码判断单向链表中有没有形成环，如果形成环，请找出环的入口处，即P点

摘要：由于要比移动的快，如果有环，一定会先进入环，而后进入环。现在问题就简单了，由于移动的距离永远是的一般，因此当遍历玩整个环长度个节点的时候正好遍历了个节点，也就是说，此时正好指向距离最远的点。首先，关于单链表中的环，一般涉及到以下问题： 1.给一个单链表，判断其中是否有环的存在； 2.如果存在环，找出环的入口点； 3.如果存在环，求出环上节点的个数； 4.如果存在环，求出链表的长度； ...

OldPanda 2019-07-01 13:56 评论0 收藏0
leetcode 链表相关题目解析

摘要：同时保有当前链表的尾部的指针以及头部的节点指针。链表可能只有部分成环这意味着。头部的引用尾部的引用始终指向尾部忽略虚假的头部链表相加原题地址。生成虚假的头部后两个链表两两相加注意进位以及保留位即可。链表是没有发生改变的。 showImg(https://segmentfault.com/img/remote/1460000018562166?w=1069&h=600); 前言本文基于...

harriszh 2019-08-26 13:38 评论0 收藏0