【算法题解】7. 反转链表

妖狐艹你老母 2024-03-30 13:36 62阅读 0赞

#### 文章目录 ####

*   *  题目
     *  解法一：迭代
     *   *  解题思路
         *  代码实现
         *  复杂度分析
     *  解法二：递归
     *   *  解题思路
         *  代码实现
         *  复杂度分析

### 题目 ###

> 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。来自：[leetcode][]

### 解法一：迭代 ###

#### 解题思路 ####

使用迭代的思路，循环遍历链表中的每一个节点，然后将当前节点 `head`指向前一个节点 `pre`，`pre` 开始时默认为 `null`，因为链表中最后一个节点的 `next`应该是 `null`。

以 `head = [1,2,3,4,5]` 为例，结果为`[5,4,3,2,1]`。

1.  先声明一个变量 `pre = null` 。  
    ![反转链表][20de421c5a734d8aa617af05a2538569.png_pic_center]
2.  先将 `head.next` 指向 `pre`, 即节点`1` 指向 `null`。然后将 `pre` 变为节点`1`，而 `head` 变为 `节点2`。  
    ![反转链表][5c2f05f83a6f4f07a13323b2d236d68e.png_pic_center]
3.  先将 `head.next` 指向 `pre`, 即`节点2` 指向 `节点1` 。然后将 `pre` 变为节点`2`，而 `head` 变为 `节点3`。  
    ![反转链表][0eab3a59372a473ea4636f521fba0c92.png_pic_center]
4.  先将 `head.next` 指向 `pre`, 即`节点3` 指向 `节点2` 。然后将 `pre` 变为节点`3`，而 `head` 变为 `节点4`。  
    ![反转链表][5607585599b64a1ba52a90326493745d.png_pic_center]
5.  先将 `head.next` 指向 `pre`, 即`节点4` 指向 `节点3` 。然后将 `pre` 变为节点`4`，而 `head` 变为 `节点5`。  
    ![反转链表][63afb12e01874b269254e6b9fd110fe9.png_pic_center]
6.  先将 `head.next` 指向 `pre`, 即`节点5` 指向 `节点4` 。然后将 `pre` 变为节点`5`，而 `head`变为 `null`。  
    ![反转链表][f1086a3109aa4c90a957e451b11d1849.png_pic_center]
7.  返回 `pre` 即为答案。  
    ![反转链表][b72b2244e05646cca75878b1b4158d41.png_pic_center]

#### 代码实现 ####

/**
     * 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 ListNode reverseList(ListNode head) {
        
            ListNode pre = null;
            // 循环遍历链表中的每一个节点
            while(head != null){
        
                // 先找出下一个节点
                ListNode nextNode = head.next;
    
                // 将head节点指向前一个进行反转
                head.next = pre;
    
                // 将 pre 指向 head
                pre = head;
    
                // 将 head 指向下一个节点，
                head = nextNode;
            }
            return pre;
        }    
    }

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

**时间复杂度** O ( n ) O(n) O(n): 需要循环每个节点，时间复杂度为节点个数 `n`。  
**空间复杂度** O ( 1 ) O(1) O(1)。

### 解法二：递归 ###

#### 解题思路 ####

**反转所有节点：** 先反转第二个（`next`）到最后一个节点，然后将反转后的最后一个节点（其实就是第二个节点）指向第一个节点，即 `next.next = head`，然后 `head.next = null` （这一步必须有，不然就会形成环路）。

**反转第二个到最后一个节点：** 先反转第三个（`next`）到最后一个节点，然后将反转后的最后一个节点（其实就是第三个节点）指向第二个节点。

以此类推，直到最后一个节点，它没有 `next` 节点，那么它的反转就是它自己，直接返回。然后按照递归路径逐层返回。  
![反转链表动图图解][4b75591f92824d8884549d65ca8ed5c4.gif_pic_center]

#### 代码实现 ####

/**
     * 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 ListNode reverseList(ListNode head) {
        
            if(head == null || head.next == null){
        
                return head;
            }
            ListNode next  = head.next;
            ListNode reverseNode = reverseList(next);
            next.next = head;
            head.next = null;
            return reverseNode;
        }  
    }

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

**时间复杂度**  O ( n ) O(n) O(n): 递归深度为n，需要逐层反转每一个节点，时间复杂度为节点个数 `n`。  
**空间复杂度**  O ( n ) O(n) O(n): 递归深度为n，空间复杂度主要取决于递归调用的栈空间，最多为 `n` 层。

[leetcode]: https://leetcode.cn/problems/reverse-linked-list/description/
[20de421c5a734d8aa617af05a2538569.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e85c6d9c3a0f421bbc36cdac5b1acb77.png
[5c2f05f83a6f4f07a13323b2d236d68e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ff02d310b0d8409ea358a93a4b1af748.png
[0eab3a59372a473ea4636f521fba0c92.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f3d1c88a407e440f90b849ae8b172efd.png
[5607585599b64a1ba52a90326493745d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9b7b7ace2a3d40b4ac1d996226284d55.png
[63afb12e01874b269254e6b9fd110fe9.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/74c2baeac5a7405a88df476d9dbc1ee4.png
[f1086a3109aa4c90a957e451b11d1849.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6ae8bfb6d60d48c096f74536b94551e3.png
[b72b2244e05646cca75878b1b4158d41.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8dc1fb0191564a28a7b92759ca6a5b06.png
[4b75591f92824d8884549d65ca8ed5c4.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7f8e207eb5064cb48c51344284277c26.gif