LCR 024. 反转链表（简单）

Posted on 2025-03-06 In 算法 Views:

1，问题描述

难度：简单

给定单链表的头节点 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 = [] 输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

注意：本题与主站 206 题相同： https://leetcode-cn.com/problems/reverse-linked-list/

2，思考过程

涉及子问题，使用自上而下的递归，使用递归直接就解答出来了

使用迭代法就是假象一个虚拟的pre（前一个）节点，与head节点、next节点进行交换

3，代码处理

import support.ListNode;

public class _LCR024反转链表 {

    // 涉及子问题，使用自上而下的递归
    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 ListNode reverseList_iteration(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;// 临时缓存下一个节点
            head.next = pre;// 本节点的下一个节点指向前节点
            pre = head;// 缓存当前节点（下次循环的，前节点）
            head = next;// 更新
        }
        return pre;
    }

    public static void main(String[] args) {
        _LCR024反转链表 lcr024 = new _LCR024反转链表();
        ListNode reverseList = lcr024.reverseList_iteration(new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, new ListNode(7, new ListNode(8, new ListNode(9, new ListNode(10)))))))))));
        while (reverseList != null) {
            System.out.println(reverseList.val);
            reverseList = reverseList.next;
        }
    }
}

// 1,2,3,4,5,6,7
// 2,1,3,4,5,6,7

4，思考过程

模式识别：一旦涉及子问题，可以用自上而下的递归和自下而上的动态规划问题