美文网首页
链表中环的入口节点

链表中环的入口节点

作者: 囧略囧 | 来源:发表于2020-02-17 10:49 被阅读0次

    题目描述

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

    解法一:

    要想知道环的入口节点,则必须至少经过该节点两次,类似于“字符流中第一个只出现一次的字符”,可以记录之前的节点,每输入一个新节点则判断其出现的次数。

    public class Solution {
        public ListNode EntryNodeOfLoop(ListNode pHead)
        {
            Set<ListNode> set = new HashSet<ListNode>();
            while(pHead != null) {
                if(!set.contains(pHead)) {
                    set.add(pHead);
                }
                else {
                    return pHead;
                }
                pHead = pHead.next;
            }
            return null;
        }
    }
    
    解法二:

    虽然解法一的时间复杂度为O(n),但是空间复杂度为O(n),考虑是否有办法减少空间复杂度。
    这个问题可以分成几部分:
    1、判断是否存在环。
    可以设置两个指针,慢指针每次只一个节点,快节点每次移动两个节点,则经过若干次循环后,若存在环则快慢节点必有相遇的时刻,否则快指针会首先到达链表尾。
    2、判断环中节点数。
    当快慢指针相遇时,另快节点保持静止,慢节点继续遍历,当快慢节点再次相遇时,便可知道环中节点数count。
    3、利用环中节点数找到换的入口节点。
    只需要设置两个慢指针m、n,另n先移动count节点,然后m、n节点同时向前移动,当m和n相遇时,便是在环的入口节点。
    时间复杂为O(n),空间复杂度O(1)

    public class Solution {
        public ListNode EntryNodeOfLoop(ListNode pHead)
        {
            if(pHead == null || pHead.next == null)
                return null;
            ListNode l1 = pHead;
            ListNode l2 = pHead;
            int count = 0;
            do{
                if(l2 == null) {
                    return null;
                }
                else {
                    l1 = l1.next;
                    l2 = l2.next.next;
                }
            }while(l1 != l2);
            do{
                count++;
                l1 = l1.next;
            }while(l1 != l2);
            l1 = pHead;
            l2 =  pHead;
            for(int i = 0; i < count; i++) {
                l2 = l2.next;
            }
            while(l1 != l2) {
                l1 = l1.next;
                l2 = l2.next;
            }
            return l1;
        }
    }
    
    解法三:
    image

    与解法二相同,我们可以设两个快慢指针m、n,通过两个指针是否相遇来判断是否含有闭环。
    但是当m和n相遇时,我们假设相遇点为B,环为顺时针,环总厂为c,环入口点到相遇点的长度为a,起点到环入口点的距离为x,m速度为n的两倍。则相遇时通过的总距离也为两倍:
    Sm=2Sn
    Sm=x+nc+a
    Sn=x+mc+a
    所以可以得到x=(n-2m-1)c+c-a
    c-a为橙色部分。
    所以我们可以令一个指针这时从起点出发,慢指针n继续前进,当两指针相遇时便为环的入口点。

    public class Solution {
        public ListNode EntryNodeOfLoop(ListNode pHead)
        {
            ListNode l1 = pHead;
            ListNode l2 = pHead;
            int count = 0;
            //检查l1和l2是否会相遇
            do{
                if(l2 == null) {
                    return null;
                }
                else {
                    l1 = l1.next;
                    l2 = l2.next.next;
                }
            }while(l1 != l2);
            //设置从头出发的指针
            l2 =  pHead;
            while(l1 != l2) {
                l1 = l1.next;
                l2 = l2.next;
            }
            return l1;
        }
    }
    
    解法四:

    断链法:
    由于题目已经确定了链表中含有环,如果允许对输入进行修改的话,可以将链表逐步断链,最后剩下的节点便为环的入口节点。

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

    相关文章

      网友评论

          本文标题:链表中环的入口节点

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