442_链表面试题精选¶

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

def reverse_list(head):
    """
    迭代法：三指针滚动
    prev → current → next_node
    每次把 current 的 next 指向 prev，然后三者都向前移一步
    """
    prev = None                            # 前驱节点（初始为None，即新链表尾部）
    curr = head                            # 当前节点

    while curr:                            # 遍历到链表尾部
        next_node = curr.next              # 先保存下一个节点（断链前必须保存！）
        curr.next = prev                   # 反转：当前节点指向前驱
        prev = curr                        # 前驱向前移
        curr = next_node                   # 当前节点向前移

    return prev                            # prev 就是新的头节点

# 递归法（理解递归非常有帮助）
def reverse_list_recursive(head):
    """
    递归：先递归到尾部，再从尾部反转回来
    """
    if not head or not head.next:          # 空链表或只有一个节点
        return head

    new_head = reverse_list_recursive(head.next)  # 先把后面全反转

    head.next.next = head                  # 让后一个节点指回当前节点
    head.next = None                       # 当前节点的next断开（变尾部）

    return new_head                        # 返回新头节点

# 辅助函数：构建和打印链表
def build_list(vals):
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next

def print_list(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    print(result)

# 测试
head = build_list([1, 2, 3, 4, 5])
print_list(reverse_list(head))    # [5, 4, 3, 2, 1]

def detect_cycle(head):
    """
    快慢指针：
    第一步：找到相遇点
    第二步：从相遇点和头节点同速出发，再次相遇处就是环入口

    数学推导：设链表头到环入口距离为a，环入口到相遇点为b，环长为c
    快指针走了 a+b+c，慢指针走了 a+b
    快=慢×2 → a+b+c = 2(a+b) → c-b = a
    所以从相遇点走a步 = 从头走a步，会在环入口相遇
    """
    slow = head                            # 慢指针：每次走1步
    fast = head                            # 快指针：每次走2步

    # 第一步：找相遇点（判断有环）
    while fast and fast.next:
        slow = slow.next                   # 慢指针走1步
        fast = fast.next.next              # 快指针走2步

        if slow == fast:                   # 相遇，说明有环
            # 第二步：找环入口
            ptr = head
            while ptr != slow:             # 两个指针同速走，相遇处是环入口
                ptr = ptr.next
                slow = slow.next
            return ptr                     # 返回环入口节点

    return None                            # 没有环

# 简化版：只判断有无环（不找入口）
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

def merge_two_lists(l1, l2):
    """
    虚拟头节点法：避免处理合并结果头节点的特殊情况
    逐个比较两链表当前节点，小的接到结果链表
    """
    dummy = ListNode(0)                    # 虚拟头节点，方便操作
    curr = dummy                           # 结果链表的构建指针

    while l1 and l2:                       # 两个链表都还有节点
        if l1.val <= l2.val:
            curr.next = l1                 # 接l1的节点
            l1 = l1.next                   # l1向前移
        else:
            curr.next = l2                 # 接l2的节点
            l2 = l2.next                   # l2向前移
        curr = curr.next                   # 结果指针向前移

    curr.next = l1 if l1 else l2           # 接上剩余部分（直接接，不用逐个复制）

    return dummy.next                      # 返回真正的头节点

# 测试
l1 = build_list([1, 2, 4])
l2 = build_list([1, 3, 4])
print_list(merge_two_lists(l1, l2))  # [1, 1, 2, 3, 4, 4]

# 链表模板
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 快慢指针找中点
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# slow 就是中点（偶数时是前半段最后一个）

# 虚拟头节点模板
dummy = ListNode(0)
dummy.next = head
# 操作结束后 return dummy.next

# 找倒数第k个节点
fast = slow = head
for _ in range(k):        # fast先走k步
    fast = fast.next
while fast:               # 再同步走，fast到尾时slow在倒数第k
    slow = slow.next
    fast = fast.next