15 反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

示例：

输入: 1->2->3->4->5
输出: 5->4->3->2->1

解题思路

核心思想：使用三个指针，逐个反转链表的指向。

关键步骤：

1. prev指向已反转部分的头（初始为None）
2. curr指向当前处理的节点（初始为head）
3. next_temp暂存curr.next
4. 反转：curr.next指向prev
5. prev移动到curr，curr移动到next_temp
6. 重复直到curr为None

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

Python 实现

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


def reverse_list(head):
    """
    反转链表

    Args:
        head: 链表头结点

    Returns:
        ListNode: 反转后的链表头结点
    """
    prev = None
    curr = head

    while curr:
        # 暂存下一个节点
        next_temp = curr.next
        # 反转
        curr.next = prev
        # 移动指针
        prev = curr
        curr = next_temp

    return 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

    return new_head


# 辅助函数：创建链表
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    p = head
    for val in arr[1:]:
        p.next = ListNode(val)
        p = p.next
    return head


# 辅助函数：打印链表
def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print('->'.join(result))


# 测试代码
if __name__ == "__main__":
    # 创建链表 1->2->3->4->5
    head = create_linked_list([1, 2, 3, 4, 5])
    print("原链表: ", end="")
    print_list(head)

    reversed_head = reverse_list(head)
    print("反转后: ", end="")
    print_list(reversed_head)

    # 测试递归版本
    head2 = create_linked_list([1, 2, 3])
    print("\n原链表: ", end="")
    print_list(head2)

    reversed_head2 = reverse_list_recursive(head2)
    print("递归反转后: ", end="")
    print_list(reversed_head2)

# 输出:
# 原链表: 1->2->3->4->5
# 反转后: 5->4->3->2->1
#
# 原链表: 1->2->3
# 递归反转后: 3->2->1

图解

迭代反转示例: 1->2->3->4->5

初始状态:
None←  1 → 2 → 3 → 4 → 5
  ↑    ↑
prev curr

步骤1:
None←  1 ← 2 → 3 → 4 → 5
       ↑   ↑
      prev curr

步骤2:
None←  1 ← 2 ← 3 → 4 → 5
           ↑   ↑
          prev curr

步骤3:
None←  1 ← 2 ← 3 ← 4 → 5
               ↑   ↑
              prev curr

步骤4:
None←  1 ← 2 ← 3 ← 4 ← 5
                   ↑   ↑
                  prev curr

步骤5: curr=None，prev指向新的头结点
返回: prev → 5