如何反转一个链表？

推荐答案

// www.javascriptcn.com code example
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head: ListNode) -> ListNode:
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

本题详细解读

问题描述

反转一个单链表。例如，给定链表 1->2->3->4->5，反转后应得到 5->4->3->2->1。

解题思路

反转链表的基本思路是通过遍历链表，逐个改变节点的指向。具体步骤如下：

1. 初始化两个指针：prev 和 curr。prev 初始化为 None，curr 初始化为链表的头节点 head。
2. 遍历链表：在遍历过程中，每次将当前节点 curr 的 next 指针指向 prev，然后将 prev 和 curr 向前移动一步。
3. 终止条件：当 curr 为 None 时，遍历结束，此时 prev 指向新的头节点。
4. 返回结果：返回 prev，即反转后的链表头节点。

代码解析

• ListNode 类定义了链表节点的结构，包含 val 和 next 两个属性。
• reverseList 函数实现了链表的反转：
  • prev 用于保存当前节点的前一个节点。
  • curr 用于遍历链表。
  • next_temp 用于临时保存当前节点的下一个节点，以便在改变 curr.next 后继续遍历。
  • 在循环中，每次将 curr.next 指向 prev，然后更新 prev 和 curr 的位置。
  • 最终返回 prev，即反转后的链表头节点。

时间复杂度

• 时间复杂度为 O(n)，其中 n 是链表的长度。因为需要遍历整个链表一次。
• 空间复杂度为 O(1)，只使用了常数级别的额外空间。