(链表专题) 206. 反转链表 ——【Leetcode每日一题】

比眉伴天荒 2024-03-24 15:38 15阅读 0赞

### 206. 反转链表 ###

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

##### 示例 1： #####

![在这里插入图片描述][836ccc56cd7748bc824cd2cd9ab8e66b.png]

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

##### 示例 2： #####

![在这里插入图片描述][229eb16d00c643aeb473c987d5b222e1.png]

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

##### 示例 3： #####

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

**提示：**

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

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

#### 思路： ####

**法一：头插法：**

*  在遍历链表时，将当前节点的 `next`指针改为指向前一个节点；
 *  由于节点没有引用其前一个节点，因此必须事先存储其前一个节点；
 *  在更改引用之前，还需要存储后一个节点；
 *  最后返回新的头引用。

**法二：递归**

*  使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 `reList`；
 *  此后，每次函数在返回的过程中，让当前结点的下一个结点的 `next` 指针指向当前节点；
 *  同时让当前结点的 `next` 指针指向 \`NULL ，从而实现从链表尾部开始的局部反转；
 *  当递归函数全部出栈后，链表反转完成。

#### 代码：(Java、C++) ####

**法一：头插法**  
**Java**

/**
     * 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 reList = null, pre = head;
            while(head != null){
        
                head = head.next;
                pre.next = reList;
                reList = pre;
                pre = head;
            }
            return reList;
        }
    }

**C++**

/**
     * 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) {
        
            ListNode* reList = NULL;
            ListNode* pre = head;
            while(head != NULL){
        
                head = head->next;
                pre->next = reList;
                reList = pre;
                pre = head;
            }
            return reList;
        }
    };

**法二：递归**

**Java**

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

**C++**

/**
     * 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) {
        //头插法
            if(head == NULL || head->next == NULL){
        
                return head;
            }
            ListNode* reList = reverseList(head->next);
            head->next->next = head;
            head->next = NULL; 
            return reList;
        }
    };

##### 运行结果： #####

![在这里插入图片描述][fd58a0337c1c425ea00a953fa1d6cb94.png]

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

*  **时间复杂度**： O ( n ) O(n) O(n)，其中 `n` 是链表的长度。需要对链表的每个节点进行反转操作。
 *  **空间复杂度**： O ( 1 ) O(1) O(1)，法一是 O ( 1 ) O(1) O(1)，法二是`O(n)`；其中 `n` 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 `n` 层。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[836ccc56cd7748bc824cd2cd9ab8e66b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3f0a6470b1394332bebf11db058c67de.png
[229eb16d00c643aeb473c987d5b222e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/4ef21b9a5df24f23aa8cdd39538f7beb.png
[fd58a0337c1c425ea00a953fa1d6cb94.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/b72c412cb5bb41a79caa12ec36d72395.png
[Link 1]: https://leetcode.cn/problems/reverse-linked-list/description/
[leetCode]: http://t.csdn.cn/kQLJO