当前位置：首页 > article >正文

Leetcode 206 -反转链表

article 2025/3/5 0:21:58

Leetcode 206: 反转链表

这是一道非常经典的链表操作题目，要求熟练掌握链表的遍历与指针操作。反转链表是面试中经常出现的题目之一，也是链表题目的基本方法题。

题目描述

输入：一个链表的头节点 head。
输出：反转后的链表，即将链表中所有的指针方向进行翻转，最后返回新的头节点。

示例

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

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

解法 1：迭代法 (双指针)

思路

使用双指针方法遍历链表：
- 一个指针 prev 表示反转后链表的头节点；
- 另一个指针 curr 指向当前节点。
反转操作：
- 每次用 curr.next = prev 更新指针，反转当前节点与前驱节点之间的指针连接；
- 然后将两个指针分别向后移动：prev = curr，curr = next。
返回链表的新头节点，即左移到最后的 prev 指针。

代码模板

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null; // 反转后链表的头，初始为 null
        ListNode curr = head; // 当前节点
        
        // 遍历链表
        while (curr != null) {
            ListNode next = curr.next; // 保存当前节点的下一个节点
            curr.next = prev;         // 反转指针连接
            prev = curr;              // 移动 prev 指针
            curr = next;              // 移动 curr 指针
        }

        return prev; // 最终 prev 成为新的头节点
    }
}

复杂度分析

时间复杂度：O(n)
- 遍历链表一次，操作与链表长度成线性关系。
空间复杂度：O(1)
- 仅使用两个指针，没有额外空间。

解法特性

优点：代码清晰，适合面试时快速实现，也是此类问题的首选解法。
适用场景：链表中无额外附加条件，线性处理。

解法 2：递归法

思路

利用函数的递归调用来构造链表的反转。
递归终止条件：
- 当前节点为 null 或到达链表的尾节点，此时返回该节点作为新的头节点。
递归返回阶段：
- 将下一节点的 next 指针指回当前节点（即 head.next.next = head），反转当前节点的指针；
- 当前节点的 next 更新为 null，从而断开后续链表。

递归返回后，新头节点会逐层归还至上层调用。

代码模板

class Solution {
    public ListNode reverseList(ListNode head) {
        // 递归终止条件，返回新的头节点
        if (head == null || head.next == null) {
            return head;
        }

        // 递归反转子链表
        ListNode newHead = reverseList(head.next);

        // 反转当前节点与下一节点之间的指针
        head.next.next = head;
        head.next = null;

        return newHead; // 返回新的头节点
    }
}

复杂度分析

时间复杂度：O(n)
- 每个节点仅被访问一次。
空间复杂度：O(n)
- 递归调用栈的深度为链表长度，最坏情况下占用 O(n) 的额外空间。

解法特性

优点：代码更加简洁，适用于强调递归能力的题目或比赛。
缺点：如果链表过长，递归调用可能导致栈溢出。

解法 3：头插法

思路

采用头插法构造反转链表：
- 使用一个新链表，将原链表的每个节点依次插入到新链表的头部。
操作步骤：
- 遍历原链表，将当前节点插入新链表的头部。
- 通过头插法不断更新反转后的链表头节点。

代码模板

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode newHead = null; // 新链表的头节点

        while (head != null) {
            ListNode next = head.next; // 保存原链表的下一个节点
            head.next = newHead;       // 当前节点插入到新链表的头部
            newHead = head;            // 更新新链表的头节点
            head = next;               // 移动到原链表的下一个节点
        }

        return newHead; // 返回新链表的头节点
    }
}

复杂度分析

时间复杂度：O(n)
- 遍历链表一次。
空间复杂度：O(1)
- 原地修改指针，无需额外的栈空间。

解法特性

优点：实现过程清晰直观，指针操作较简单。
缺点：需要关联到新链表概念，与解法 1 类似，但不直接操作原链表头节点。

解法 4：栈

思路

利用栈的 后进先出 (LIFO) 特性存储链表节点。
遍历链表时依次将所有节点压入栈。
依次弹出栈构造新的链表。

代码模板

import java.util.Stack;

class Solution {
    public ListNode reverseList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }

        // 构造新的反转链表
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (!stack.isEmpty()) {
            curr.next = stack.pop();
            curr = curr.next;
        }
        curr.next = null; // 手动置尾节点的 next 为 null

        return dummy.next;
    }
}