核心要点

  • 反转链表：用 prev/cur/next 三指针，逐个把当前节点的 next 指向前驱

  • 环检测：Floyd 快慢指针，slow 走一步、fast 走两步，相遇说明有环

  • 复杂度：反转 O(n) 时间 O(1) 空间；判环 O(n) 时间 O(1) 空间

标准回答

链表反转和环检测是最常考的链表题。反转用三指针法：保存当前节点的下一个，再把当前节点的 next 指向前驱，然后整体右移，遍历一遍即可原地反转，空间 O(1)。环检测用 Floyd 判圈算法（快慢指针）：慢指针每次走一步、快指针走两步，若存在环则两者必在环内相遇（追及问题），无环则快指针先到达链尾的空节点。下面给出两者实现：

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


def reverse_list(head):
    # 三指针原地反转
    prev = None
    cur = head
    while cur:
        nxt = cur.next      # 1. 暂存后继
        cur.next = prev     # 2. 翻转指针指向前驱
        prev = cur          # 3. prev 前移
        cur = nxt           # 4. cur 前移
    return prev             # prev 是新的头节点


def has_cycle(head):
    # Floyd 快慢指针判环
    slow = fast = head
    while fast and fast.next:
        slow = slow.next        # 慢指针走一步
        fast = fast.next.next   # 快指针走两步
        if slow is fast:        # 相遇说明有环
            return True
    return False                # fast 到尾，无环


if __name__ == '__main__':
    # 1->2->3 反转为 3->2->1
    head = ListNode(1, ListNode(2, ListNode(3)))
    r = reverse_list(head)
    out = []
    while r:
        out.append(r.val)
        r = r.next
    print(out)               # [3, 2, 1]

    # 构造带环链表 a->b->c->a
    a, b, c = ListNode(1), ListNode(2), ListNode(3)
    a.next, b.next, c.next = b, c, a
    print(has_cycle(a))      # True
    print(has_cycle(ListNode(1, ListNode(2))))  # False

常见误区

⚠️ 常见踩坑

反转时若不先暂存 cur.next 就改指针，会丢失后续链表；判环循环条件必须是 fast and fast.next，否则在无环偶数长度链表上访问 None.next 报错。

追问

追问 1：如何找到环的入口节点？

Floyd 第二阶段：快慢指针首次相遇后，让一个指针回到头节点，两指针都每次走一步，再次相遇处即为环入口。数学上可证明：头到入口的距离等于相遇点继续走到入口的距离。

追问 2：反转链表能用递归实现吗？复杂度如何？

可以。递归到链尾返回新头，回溯时令 head.next.next = head、head.next = None。时间仍 O(n)，但递归栈占用 O(n) 空间，劣于迭代的 O(1)，且长链表可能栈溢出。

延伸学习

与本题相关的知识库文章、术语、工具与行业资讯。

🎯 相关面试题