链表——找到入环第一个节点(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