链表中环的入口节点

栏目: 数据库 · 发布时间: 5年前

内容简介:给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。遍历链表的时候,用一个容器list依次装入链表的节点,如果发现有重复的节点,那么就是链表的环的入口节点时间复杂度:O(n^2)

题目描述

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出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<ListNode> 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》——链表中环的入口结点


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

区块链

区块链

长铗、韩锋 / 中信出版社 / 2016-7 / CNY 58.00

《区块链:从数字货币到信用社会》从历史与背景、发展现状、基础原理与技术、应用生态、存在的问题与挑战等方面论述了区块链是怎样立起来的,为什么人人都在谈论区块链,区块链的秘密在哪里、进阶区块链(第二代区块链技术)是什么,区块链怎么玩,怎样从信息互联网走向价值互联网,如何用法规约束和监管区块链,区块链走向何处、争议与挑战,并通过经济、金融、货币、法律、科技哲学等角度来加以分析区块链在各个方面遇到的问题和......一起来看看 《区块链》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

URL 编码/解码
URL 编码/解码

URL 编码/解码