高频面试题之链表专题-逆置一个单链表

青旅半醒 2022-10-16 06:09 137阅读 0赞

# 逆置一个单链表  #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70][]

OJ链接：[https://leetcode-cn.com/problems/reverse-linked-list/description/][https_leetcode-cn.com_problems_reverse-linked-list_description]

### **高频考察的大厂云图** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1][]

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

示例 1：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 2][]

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

示例 2：

![20210527111924125.png][]

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

示例 3：

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

提示：

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

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

### 提供代码 ###

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode() : val(0), next(nullptr) {}
     *     ListNode(int x) : val(x), next(nullptr) {}
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}
     * };
     */
    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
    
        }
    };

### 解题思路 ###

1. 三指针翻转法：记录连续的三个节点，原地修改节点指向的方向。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 3][]

2. 头插法：取下原链表的每个节点都进行头插到新链表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 7][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 8][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 9][]

............

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

三指针翻转法

#include<iostream>
    using namespace std;
    struct ListNode {
        int val;
        ListNode* next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode* next) : val(x), next(next) {}
    };
     
    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            if (head == NULL)
                return NULL;
            ListNode* n1, * n2, * n3;
            n1 = NULL;
            n2 = head;
            n3 = head->next;
    
            //翻转
            while (n2 != NULL)
            {
                n2->next = n1;
                n1 = n2;
                n2 = n3;
                if (n3 != NULL)
                    n3 = n3->next;
            }
            return n1;
        }
    };

头插法

#include<iostream>
    using namespace std;
    struct ListNode {
        int val;
        ListNode* next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode* next) : val(x), next(next) {}
    };
     
    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            ListNode* cur = head;
            ListNode* newhead = NULL;
    
            while (cur != NULL)
            {
                //保存下一个
                ListNode* next = cur->next;
                //头插
                cur->next = newhead;
                newhead = cur;
    
                cur = next;
            }
            return newhead;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70]: /images/20221014/dafd6da41f7a4bdd896dc0604137af2b.png
[https_leetcode-cn.com_problems_reverse-linked-list_description]: https://leetcode-cn.com/problems/reverse-linked-list/description/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1]: /images/20221014/bb3c0d4982004d4e92776491b2cb276b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 2]: /images/20221014/540fe617902c4d8a90b7831f04170e08.png
[20210527111924125.png]: /images/20221014/647cc09222cd4d12bb01f6968140ba14.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 3]: /images/20221014/5f401d7e79e24b1f8abb4f713b6718f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 4]: /images/20221014/cb2e040220f54d3599e8f5f61b279a8d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 5]: /images/20221014/2d91eaff9b884dae9ac6978adc10aa86.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 6]: /images/20221014/f10b4f44e3a64f03972c31a8857e62ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 7]: /images/20221014/64a738edd2a848fc9c064942d4f736e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 8]: /images/20221014/d3affb5a406646b68411b28e82d7904c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 9]: /images/20221014/fb5c845a00c0473b8272ac574f34829d.png