「力扣」第 142 题:环形链表 II(中等)
链接:https://leetcode-cn.com/problems/linked-list-cycle-ii
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
说明:不允许修改给定的链表。
示例 1:
输入:head = [3,2,0,-4], pos = 1 输出:tail connects to node index 1 解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0 输出:tail connects to node index 0 解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1 输出:no cycle 解释:链表中没有环。
进阶:
你是否可以不用额外空间解决此题?
Java 代码:
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
public ListNode(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("arr can not be empty");
}
this.val = nums[0];
ListNode curr = this;
for (int i = 1; i < nums.length; i++) {
curr.next = new ListNode(nums[i]);
curr = curr.next;
}
}
@Override
public String toString() {
StringBuilder s = new StringBuilder();
ListNode cur = this;
while (cur != null) {
s.append(cur.val);
s.append(" -> ");
cur = cur.next;
}
s.append("NULL");
return s.toString();
}
}
public class Solution {
public ListNode detectCycle(ListNode head) {
// 特判
if (head == null || head.next == null) {
// 注意:不要习惯性把 head 返回回去
return null;
}
// 起点要一样,这里第 141 题的结论
ListNode slow = head;
ListNode fast = head;
// 注意这种写法,因为快指针一次走两步,
// 所以要看它下一个结点以及下下一个结点是否为空
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
// 特判,如果只是因为链表不存在环,那就返回空,因为既然不存在环,肯定没有重复结点
if (fast.next == null || fast.next.next == null) {
return null;
}
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
Python 代码:
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return None
slow = head
fast = head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
break
if fast.next is None or fast.next.next is None:
return None
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow