精选力扣500题第1题 LeetCode 206. 反转链表【c++详细题解】

ゞ浴缸里的玫瑰 2021-07-24 21:45 364阅读 0赞

### 目录 ###

*   *   *  题目
         *  思路
         *  代码

### 题目 ###

原题链接：**[206. 反转链表][206.]**

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

**示例 1：**

![img][]

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

**示例 2：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70][]

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

**示例 3：**

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

**提示：**

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

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

### 思路 ###

翻转即将所有节点的`next`指针指向前驱节点。  
由于是单链表，我们在迭代时不能直接找到前驱节点，所以我们需要一个额外的指针保存前驱节点。同时在改变当前节点的`next`指针前，不要忘记保存它的后继节点。

**空间复杂度分析** 遍历时只有3个额外变量，所以额外的空间复杂度是  O ( 1 ) O(1) O(1)。  
**时间复杂度分析** 只遍历一次链表，时间复杂度是  O ( n ) O(n) O(n)。

### 代码 ###

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
     /*======= 非递归版 ====== */
    
    class Solution { 
    public:
        ListNode* reverseList(ListNode* head) { 
            ListNode* prev = NULL; //当前节点的前驱节点
            ListNode* cur = head;  //当前节点
    
            while(cur)
            { 
                ListNode* next = cur->next; //首先保存当前节点的后继节点
                cur->next = prev; //将当前节点指向它的前驱节点
                prev = cur, cur = next; //节点后移
            }
            return prev;
        }
    };

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

[206.]: https://leetcode-cn.com/problems/reverse-linked-list/
[img]: /images/20210724/f176b0c5104748d281d9f9ce71485d84.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/7bba66466db74d2192d212cca9ded70a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/0aaee4872a234d9b8876b8f56914a6de.png