55 链表中环的入口结点

题目描述

给一个链表，若其中包含环，请找出入口节点，否则，返回null。

解题思路

核心思想：快慢指针法。

关键步骤：

1. 使用快慢指针判断是否有环
2. 如果有环，让一个指针回到头，另一个指针继续
3. 两个指针同时移动，相遇点即为入口

时间复杂度：O(n) 空间复杂度：O(1)

Python 实现

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def entry_node_of_loop(head):
    """
    找出链表中环的入口节点

    Args:
        head: 链表头节点

    Returns:
        ListNode: 入口节点，无环返回None
    """
    if not head or not head.next or not head.next.next:
        return None

    # 快慢指针找相遇点
    slow = head.next
    fast = head.next.next

    while slow != fast:
        if not fast or not fast.next:
            return None
        slow = slow.next
        fast = fast.next.next

    # 一个指针回到头
    slow = head

    # 同时移动，相遇点为入口
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow


# 测试代码
if __name__ == "__main__":
    # 创建带环的链表: 1->2->3->4->5->3（环）
    node3 = ListNode(3)
    node4 = ListNode(4)
    node5 = ListNode(5)

    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = node3
    node3.next = node4
    node4.next = node5
    node5.next = node3  # 形成环

    entry = entry_node_of_loop(head)
    if entry:
        print(f"环的入口节点: {entry.val}")
    else:
        print("无环")

图解

示例: 1->2->3->4->5->3（环）

快慢指针:
slow: 1→2→3→4→5→3→4...
fast: 2→4→3→5→4→3...

在节点4相遇

slow回到头:
slow: 1→2→3...
fast: 4→5→3...

在节点3相遇，这是环的入口

---