内容简介:给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出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)
参考
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Dreamweaver基础教程
李振华、季小武、季小武、李振华 / 清华大学 / 2005-6 / 23.00元
本书通过实例的方式介绍了Macromedia公司的Dreamweaver MX 2004的使用方法和技巧。 全书由14章组成,第1章和第2章介绍了软件的应用领域、知识结构、界面组成等;第3章到第12章是本书的重点部分,通过实例制作介绍了站点的建立,表格、文本及样式的创建,链接、图像、行为的使用,层、表单、框架的创建和使用以及动画、多媒体的制作等主要知识点;第13章和第14章介绍了插件技......一起来看看 《Dreamweaver基础教程》 这本书的介绍吧!
在线进制转换器
各进制数互转换器
RGB HSV 转换
RGB HSV 互转工具