【LeetCode】18. Reverse Linked List·反转链表

喜欢ヅ旅行 2024-04-08 09:08 78阅读 0赞

> 活动地址：[CSDN21天学习挑战赛][CSDN21]

## 题目描述 ##

### 英文版描述 ###

Given the head of a singly linked list, reverse the list, and return the reversed list.

### 英文版地址 ###

https://leetcode.com/problems/reverse-linked-list/

### 中文版描述 ###

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

> 示例 1：
> 
> 输入：head = \[1,2,3,4,5\]
> 
> 输出：\[5,4,3,2,1\]
> 
> 示例 2：
> 
> 输入：head = \[1,2\]
> 
> 输出：\[2,1\]
> 
> 示例 3：
> 
> 输入：head = \[\]
> 
> 输出：\[\]

提示：

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

### 中文版地址 ###

https://leetcode.cn/problems/reverse-linked-list/

## 解题方法 ##

### 俺这版 ###

![7941e3b0bc579fa85940e0b36990d85a.png][]

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
          public static ListNode reverseList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode listNode = reverseList(head.next);
            head.next.next = head;
            head.next = null;
            return listNode;
        }
    }

#### 复杂度分析 ####

*  时间复杂度：O(n)，其中 n是链表的长度，每个节点需要执行一次操作
 *  空间复杂度：O(n)，递归栈的深度取决于链表的长度

### 官方版 ###

官方提供了两种方法，一种是递归，跟我的基本一致，就不贴叻，还有一种是迭代

> 假设链表为 1→2→3→∅，我们想要把它改成∅←1←2←3。 在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

![66a41a9b271c186d11c8ce852db659e2.png][]

class Solution {
        public ListNode reverseList(ListNode head) {
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null) {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            return prev;
        }
    }

#### 复杂度分析 ####

*  时间复杂度：O(n)，其中 n是链表的长度，需要遍历链表一次
 *  空间复杂度：O(3) = O(1)

## 总结 ##

个人感觉迭代使用指针相比递归简单点点，将3个指针从链表开端移动到链表结尾，当l链表较长时，节省了很大的空间

[CSDN21]: https://marketing.csdn.net/p/bdabfb52c5d56532133df2adc1a728fd
[7941e3b0bc579fa85940e0b36990d85a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/3472418257a54e79bcf14148b599fd66.png
[66a41a9b271c186d11c8ce852db659e2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/d9e5838a8bfc4ea9943b512c1996659f.png