06 | 面试题：反转一个单链表&判断链表是否有环

在算法面试中，链表作为数据结构的基础之一，经常成为考察的重点。其中，反转单链表和判断链表是否有环是两个非常典型的题目，它们不仅考验了面试者对链表操作的基本功，还涉及到递归、迭代、快慢指针等多种算法思想的运用。本章节将详细探讨这两个问题的解法，并通过代码示例帮助读者深入理解。

一、反转一个单链表

1. 问题描述

给定一个单链表的头节点 head，要求原地反转链表中的所有节点，并返回反转后的链表头节点。

2. 解题思路

• 迭代法：通过迭代的方式，逐个遍历链表节点，同时调整每个节点的 next 指针指向其前一个节点，直至遍历完成。迭代过程中需要保存当前节点的下一个节点，以防链表断开。
• 递归法：利用递归的调用栈来保存遍历过程中的节点信息，递归的终止条件是到达链表末尾。在递归返回过程中，逐步调整节点的 next 指针，实现反转。

3. 迭代法实现

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def reverseListIteratively(head):
    prev = None
    current = head
    while current:
        next_temp = current.next  # 保存当前节点的下一个节点
        current.next = prev       # 反转当前节点的next指针
        prev = current            # 移动prev和current
        current = next_temp
    return prev  # 当遍历完成时，prev即为新的头节点
# 示例
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
reversed_head = reverseListIteratively(head)
# 验证反转结果
while reversed_head:
    print(reversed_head.val, end=" ")
    reversed_head = reversed_head.next
# 输出: 5 4 3 2 1

4. 递归法实现

def reverseListRecursively(head):
    if not head or not head.next:
        return head
    new_head = reverseListRecursively(head.next)
    head.next.next = head  # 反转当前节点与下一个节点的连接
    head.next = None       # 将当前节点的next指针置为None，防止成环
    return new_head
# 示例同上，使用递归函数
reversed_head_recursive = reverseListRecursively(head)
# 验证反转结果（同上）

二、判断链表是否有环

1. 问题描述

给定一个单链表的头节点 head，要求判断链表中是否存在环。

2. 解题思路

• 快慢指针法（Floyd判圈算法）：使用两个指针，一个快指针（每次移动两步）和一个慢指针（每次移动一步）。如果链表中存在环，那么快慢指针最终会在环内相遇；如果链表无环，那么快指针会先到达链表末尾。
• 哈希表法：遍历链表，将访问过的节点存储在哈希表中。若遇到已存在于哈希表中的节点，则说明链表有环；若遍历完成未遇到重复节点，则链表无环。但这种方法会占用额外的空间。

3. 快慢指针法实现

def hasCycle(head):
    if not head or not head.next:
        return False
    slow = head
    fast = head.next
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    return True
# 示例
# 假设存在一个有环的链表
# head -> 1 -> 2 -> 3 -> 4 -> 5 -> 3 (环开始于节点3)
# 判断环的存在
has_cycle = hasCycle(head_with_cycle)  # 假设head_with_cycle为上述有环链表的头节点
print(has_cycle)  # 输出: True

三、总结

本章节详细讲解了反转单链表和判断链表是否有环两个问题的解题思路与实现方法。反转单链表通过迭代和递归两种方式实现，各有优劣，迭代法空间复杂度低但代码相对冗长，递归法代码简洁但可能面临栈溢出的风险。判断链表是否有环则主要介绍了快慢指针法，该方法以其高效的空间利用率和清晰的逻辑成为解决此类问题的首选。通过这两个问题的探讨，读者不仅能加深对链表操作的理解，还能掌握递归、迭代、快慢指针等算法思想的应用。