206. 反转链表

题目描述

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

---

示例

示例 1：

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

示例 2：

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

示例 3：

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

---

解题思路

1. 双指针法（迭代法）

• 思想：

  • 使用两个指针：prev 和 curr。
  • prev 初始化为 null，curr 指向链表的头节点。
  • 遍历链表时，将 curr 的 next 指针指向 prev，完成反转。
  • 然后移动两个指针，直到 curr 为 null。

• 步骤：

  1. 初始化两个指针：prev = null，curr = head。
  2. 遍历链表：对于当前节点 curr：
     • 保存下一节点：nextTemp = curr.next。
     • 修改 curr.next 指向 prev。
     • 将 prev 和 curr 分别向前移动一步。
  3. 最终，prev 指针指向新的链表头部。

• 时间复杂度：

  • 每个节点只被访问一次，时间复杂度为 (O(n))。

• 空间复杂度：

  • 只使用了额外的指针，空间复杂度为 (O(1))。

2. 递归法

• 思想：

  • 递归的本质是利用栈，反转链表时，从链表的尾部逐步向头部修改指针。
  • 递归的返回条件是当前节点为空，或者当前节点是尾节点。
  • 当从递归中返回时，修改 next 节点的 next 指针，指向当前节点，实现链表反转。

• 步骤：

  1. 递归找到链表的最后一个节点。
  2. 从最后一个节点开始逐步修改指针，反转链表。
  3. 最后返回新的头节点。

• 时间复杂度：

  • 每个节点访问一次，时间复杂度为 (O(n))。

• 空间复杂度：

  • 递归调用的栈空间是 (O(n))，因此总体空间复杂度为 (O(n))。

---

代码实现

方法 1：迭代法

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取链表节点值
        String[] values = scanner.nextLine().split(" ");
        ListNode head = null;
        ListNode tail = null;
        for (String val : values) {
            if (!val.isEmpty()) {
                ListNode newNode = new ListNode(Integer.parseInt(val));
                if (head == null) {
                    head = newNode;
                    tail = newNode;
                } else {
                    tail.next = newNode;
                    tail = newNode;
                }
            }
        }

        Solution solution = new Solution();
        ListNode reversedHead = solution.reverseList(head);

        // 输出反转后的链表
        while (reversedHead != null) {
            System.out.print(reversedHead.val + " ");
            reversedHead = reversedHead.next;
        }
        System.out.println();

        scanner.close();
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null; // 初始化前驱节点为 null
        ListNode curr = head; // 当前节点从头节点开始

        while (curr != null) {
            ListNode nextTemp = curr.next; // 保存当前节点的下一个节点
            curr.next = prev; // 将当前节点的指针指向前驱节点
            prev = curr; // 更新前驱节点为当前节点
            curr = nextTemp; // 更新当前节点为原来的下一个节点
        }

        return prev; // 返回反转后的新头节点
    }
}

// 定义链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

方法 2：递归法

public class ReverseLinkedList {
    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; // 返回新的头节点
    }

    // 定义链表节点类
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static void main(String[] args) {
        ReverseLinkedList solution = new ReverseLinkedList();

        // 构造测试链表
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        // 反转链表并打印结果
        ListNode reversedHead = solution.reverseList(head);
        while (reversedHead != null) {
            System.out.print(reversedHead.val + " ");
            reversedHead = reversedHead.next;
        }
    }
}

---

测试用例

1. 普通链表：

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

2. 只有一个节点的链表：

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

3. 空链表：

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

4. 边界情况：

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

---

注意事项

1. 原地修改链表：

   • 无论是迭代还是递归，都需要直接修改链表的指针，而不是重新构造链表。

2. 递归栈溢出：

   • 如果链表非常长（如超过 10,000 个节点），递归方法可能会导致栈溢出。因此，迭代方法更为安全。

---