【图解 LeetCode】206：反转吧，链表！

快来打我* 2022-09-09 15:49 121阅读 0赞

大家好呀，我是蛋蛋。

今天整**反转链表**，它没有太多思维上的难度，但是出现频率极高。

可以这么说，不管什么时候，只要考到链表，反转链表都属于必考项。

话不多说，直接开工。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_18_color_FFFFFF_t_70_g_se_x_16_pic_center]

--------------------

### LeetCode 206：反转链表 ###

#### 题意 ####

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

#### 示例 ####

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

输出：\[5, 4, 3, 2, 1\]

注意，如果是空链表

输入：head = \[\]

输出：\[\]

#### 提示 ####

0 <= 链表节点数 <= 5000

\-5000 <= Node.val <= 5000

#### 题目解析 ####

水题，难度简单。

题目没有思维上的难度，就是**把每个节点的 next 指向它的前驱节点即可。**

**主要考察臭宝写代码的能力。**

#### 图解 ####

这个题是将当前 next 节点的指针指向它的前驱节点，这就需要得有两个指针：一个指向当前节点，一个指向前驱节点。  
![在这里插入图片描述][8f4eaf54cb0f408aa1906f8c6c0795fe.png_pic_center]  
如果只有这俩的话又不对，因为当 p 的 next 指针指向前驱节点 q 的时候，上图就会变成这样：

![在这里插入图片描述][7c7bf1dcc68d438faf079dec91bf8b74.png_pic_center]  
所以此时应该还需要一个临时指针 temp，保存当前节点的后继节点，也就是如下图：

![在这里插入图片描述][746fd82d1a92447ab2e9c47ec49428f7.png_pic_center]  
所以现在成了，先找到 temp，然后 p.next 再指向 q，最后 q，p 同时右移。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]  
如此反复，直至全部结束。

本方法遍历一遍链表，所以时间复杂度为 O(n)，需要了额外的 3 个指针，空间复杂度为 O(1)。

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

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def reverseList(self, head: ListNode) -> ListNode:
    
            # 空链表或者只有一个节点，直接返回
            if not head or head.next == None:
                return head
    
            # 初始化记录当前节点 p 和前驱节点 q
            p = head
            q = None
    
            while p:
                temp = p.next
                p.next = q
                q = p
                p = temp
                
            # 最后一步，p 肯定是指向 NULL，所以返回 q 作为新的头指针
            return q

--------------------

好啦，图解反转链表到这就结束啦。

还是那句话，这类题思维上没难度，考的是代码实现，臭宝们一定要多多练习，代码熟记，最好形成肌肉记忆。

看到这的都是真爱，**一键三连**让我飘起来！

我是帅蛋，我们下次见！

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_18_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220829/8a799594a5704049af76f2e911da3b06.png
[8f4eaf54cb0f408aa1906f8c6c0795fe.png_pic_center]: /images/20220829/dbc37f4b190d42c8a0f15bcd876a4fb2.png
[7c7bf1dcc68d438faf079dec91bf8b74.png_pic_center]: /images/20220829/71c07c3abfb74316ab51e72bb9fc0308.png
[746fd82d1a92447ab2e9c47ec49428f7.png_pic_center]: /images/20220829/5e7e9e49a26e4cb98c492ea945e2dd6d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220829/345ecac9f5fa48bbb3b49dd499042f0b.png