内容简介：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出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)
参考
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
大思维：集体智慧如何改变我们的世界
杰夫·摩根 / 郭莉玲、尹玮琦、徐强 / 中信出版集团股份有限公司 / 2018-8-1 / CNY 65.00
智能时代，我们如何与机器互联，利用技术来让我们变得更聪明？为什么智能技术不会自动导致智能结果呢？线上线下群体如何协作？社会、政府或管理系统如何解决复杂的问题？本书从哲学、计算机科学和生物学等领域收集见解，揭示了如何引导组织和社会充分利用人脑和数字技术进行大规模思考，从而提高整个集体的智力水平，以解决我们时代的巨大挑战。是英国社会创新之父的洞见之作，解析企业、群体、社会如何明智决策、协作进化。一起来看看 《大思维：集体智慧如何改变我们的世界》 这本书的介绍吧!
