206.反转链表

发表于 分类于 阅读次数：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

1
2
输入：head = [1,2]
输出：[2,1]

示例 3：

1
2
输入：head = []
输出：[]

解题思路

这是一道经典的链表操作题目，考察对链表指针操作的理解。

核心思想

  • 使用三个指针：prev、curr、next
  • 逐个反转每个节点的next指针
  • 最终返回新的头节点

方法一：迭代法（推荐）

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let prev = null;
    let curr = head;
    
    while (curr !== null) {
        // 保存下一个节点
        const next = curr.next;
        
        // 反转当前节点的指针
        curr.next = prev;
        
        // 移动指针
        prev = curr;
        curr = next;
    }
    
    return prev;
};

方法二：递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var reverseList = function(head) {
    // 递归终止条件
    if (head === null || head.next === null) {
        return head;
    }
    
    // 递归反转剩余部分
    const newHead = reverseList(head.next);
    
    // 反转当前节点
    head.next.next = head;
    head.next = null;
    
    return newHead;
};

方法三：优化版本

1
2
3
4
5
6
7
8
9
10
11
12
var reverseList = function(head) {
    if (!head || !head.next) return head;
    
    let prev = null;
    let curr = head;
    
    while (curr) {
        [curr.next, prev, curr] = [prev, curr, curr.next];
    }
    
    return prev;
};

方法四：使用数组（不符合要求，但思路清晰）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var reverseList = function(head) {
    if (!head) return null;
    
    // 将链表转换为数组
    const arr = [];
    let curr = head;
    
    while (curr) {
        arr.push(curr.val);
        curr = curr.next;
    }
    
    // 反转数组
    arr.reverse();
    
    // 重新构建链表
    const newHead = new ListNode(arr[0]);
    let newCurr = newHead;
    
    for (let i = 1; i < arr.length; i++) {
        newCurr.next = new ListNode(arr[i]);
        newCurr = newCurr.next;
    }
    
    return newHead;
};

解题要点

  1. 迭代法：

    • 使用三个指针：prev、curr、next
    • 逐个反转每个节点的next指针
    • 注意保存下一个节点，避免丢失

  2. 递归法：

    • 递归反转剩余部分
    • 反转当前节点与下一个节点的关系
    • 设置当前节点的next为null

  3. 边界处理：

    • 空链表：返回null
    • 只有一个节点：返回该节点

面试要点

  • 高频考点：这道题是面试中的高频题目
  • 指针操作：考察对链表指针操作的理解
  • 递归思维：考察递归解决问题的能力
  • 空间复杂度：要求O(1)空间复杂度

相关题目

扩展思考

  1. 为什么使用三个指针？

    • prev：指向已反转部分的头节点
    • curr：当前要反转的节点
    • next：保存下一个节点，避免丢失

  2. 时间复杂度分析

    • 迭代法：O(n)
    • 递归法：O(n)
    • 空间复杂度：O(1) vs O(n)

  3. 递归vs迭代

    • 迭代：空间复杂度O(1)，更高效
    • 递归：代码更简洁，但需要栈空间

  4. 边界情况

    • 空链表：返回null
    • 只有一个节点：返回该节点
    • 两个节点：交换位置

  5. 实际应用

    • 链表排序算法
    • 链表回文判断
    • 链表分组操作

  6. 变种问题

    • 反转指定区间
    • 分组反转
    • 部分反转

最后更新: 2021-09-24