142 环形链表 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
解释:链表中没有环。

进阶:

你是否可以不用额外空间解决此题?


实现

第一种:利用暴力匹配的方式

  • 状态:通过
  • 16 / 16 个通过测试用例
  • 执行用时: 412 ms, 在所有 C# 提交中击败了 17.07% 的用户
  • 内存消耗: 24.8 MB, 在所有 C# 提交中击败了 10.00% 的用户
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode DetectCycle(ListNode head)
    {
        if (head == null)
            return null;

        ListNode p1 = head;
        int i = 0;
        while (p1 != null)
        {
            p1 = p1.next;
            i++;

            ListNode p2 = head;
            int j = 0;
            while (j < i)
            {
                if (p2 == p1)
                {
                    return p2;
                }
                p2 = p2.next;
                j++;
            }
        }
        return null;
    }
}

第二种:通过集合的方法

C# 语言

  • 状态:通过
  • 16 / 16 个通过测试用例
  • 执行用时: 140 ms, 在所有 C# 提交中击败了 82.93% 的用户
  • 内存消耗: 26 MB, 在所有 C# 提交中击败了 5.00% 的用户
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution 
{
    public ListNode DetectCycle(ListNode head) 
    {
        HashSet<ListNode> h = new HashSet<ListNode>();
        ListNode temp = head;
        while (temp != null)
        {            
            if (h.Contains(temp))
                return temp;

            h.Add(temp);
            temp = temp.next;
        }
        return null;  
    }
}

Python 语言

  • 执行结果:通过
  • 执行用时:72 ms, 在所有 Python3 提交中击败了 36.52% 的用户
  • 内存消耗:17.2 MB, 在所有 Python3 提交中击败了 7.69% 的用户
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        h = set()
        temp = head
        while temp is not None:
            if temp in h:
                return temp

            h.add(temp)
            temp = temp.next
        return None
浙ICP备19012682号