链表——找到入环第一个节点
程序员文章站
2022-05-04 14:23:49
链表——找到入环第一个节点(Leetcode.142)题目:给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。说明:不允许修改给定的链表。1、笔试(额外容器)笔试:使用额外容器——HashSet由于单链表只有一个next指针,所以如果一个单链表在某一节点入环了,那么它就不可能再跳出这个环了利用 HashSet 的元素唯一性,根据 next 指针指向将节点依次存入 set,当判断 set 中有重复节点的时候。即为第一个入环节点使用hashset结构,时间复杂度O(N...
链表——找到入环第一个节点(Leetcode.142)
题目:给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
。
说明:不允许修改给定的链表。
1、笔试(额外容器)
笔试:使用额外容器——HashSet
- 由于单链表只有一个next指针,所以如果一个单链表在某一节点入环了,那么它就不可能再跳出这个环了
- 利用 HashSet 的元素唯一性,根据 next 指针指向将节点依次存入 set,当判断 set 中有重复节点的时候。即为第一个入环节点
- 使用hashset结构,时间复杂度O(N),额外空间复杂度O(N)
代码实现:
public class GetLoopNode {
public static class ListNode{
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode detectCycle(ListNode head) {
ListNode loopNode = null;
ListNode curNode = head;
LinkedList<ListNode> listNodes = new LinkedList<ListNode>();
while (curNode != null){
if (!listNodes.contains(curNode)){
listNodes.add(curNode);
curNode = curNode.next;
}else {
loopNode = curNode;
break;
}
}
return loopNode;
}
}
2、面试(快慢指针)
面试:使用快慢指针
- 如果head为null,或者长度为1,或者无环,都应该返回 null;
- 如果存在环,快指针就会首先进入环,并不断在环内循环,且一定会在某处遇到慢指针;
- 相遇之时,用另外一个指针从 head 开始出发,和慢指针一起一次走一步,最终此指针和慢指针相交位置就是第一个入环节点;
- 关于追及问题,好像是小学奥赛题。数学推导证明:https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/
代码实现:
public class GetLoopNode {
public static class ListNode{
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null){
slow = slow.next;
//如果 fast 走向 null,说明必然无环
if (fast.next != null){
fast = fast.next.next;
}else {
return null;
}
//如果存在相交节点,则必然存在环,找到入环节点即可
if (fast == slow){
ListNode ptr = head;
while (ptr != slow){
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}
}
本文地址:https://blog.csdn.net/qq_42583242/article/details/109561077
推荐阅读
-
链表——找到入环第一个节点
-
leetcode 160剑指offer面试题52. 两个链表的第一个公共节点(python3)
-
【数据结构】给定一个链表,判定链表是否有环,如果有,返回链表开始入环的第一个节点, 如果链表无环,则返回 null。
-
Leetcode打卡五:对于一个给定的链表,返回环的入口节点,如果没有环,返回null 拓展: 你能给出不利用额外空间的解法么?
-
(三)剑指offer35 两个链表的第一个公共节点
-
#剑指offer#链表中环的入口节点:1,设置一个快的指针,一个慢的指针,若相遇,代表有环 2、设置新的指针,和慢指针再次重合即为节点
-
CCI 2.6 寻找有环链表环路的开头节点
-
双指针-链表-面试题52. 两个链表的第一个公共节点
-
链表——找到入环第一个节点
-
js中找到两个链表的第一个公共结点的算法