0206. 反转链表 · ttttt

# 0206. 反转链表 ## 题目地址(206. 反转链表) <https://leetcode-cn.com/problems/reverse-linked-list/> ## 题目描述反转一个单链表。 ``` <pre class="calibre18">``` 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？ ``` ``` ## 前置知识 - [链表](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) ## 公司 - 阿里 - 百度 - 腾讯 - adobe - amazon - apple - bloomberg - facebook - microsoft - snapchat - twitter - uber - yahoo - yelp - zenefits ## 思路这个就是常规操作了，使用一个变量记录前驱 pre，一个变量记录后继 next. 不断更新`current.next = pre` 就好了 ## 关键点解析 - 链表的基本操作（交换） - 虚拟节点 dummy 简化操作 - 注意更新 current 和 pre 的位置，否则有可能出现溢出 ## 代码语言支持：JS, C++, Python,Java JavaScript Code： ``` <pre class="calibre18">``` /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function (head) { if (!head || !head.next) return head; let cur = head; let pre = null; while (cur) { const next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; }; ``` ``` C++ Code： ``` <pre class="calibre18">``` /** * 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; ListNode* next = NULL; while (cur != NULL) { next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head: return None prev = None cur = head while cur: cur.next, prev, cur = prev, cur, cur.next return prev ``` ``` Java Code: ``` <pre class="calibre18">``` /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null, cur = head; while (cur != null) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } } ``` ``` **复杂度分析** - 时间复杂度：O(N)O(N)O(N) - 空间复杂度：O(1)O(1)O(1) ## 拓展通过单链表的定义可以得知，单链表也是递归结构，因此，也可以使用递归的方式来进行 reverse 操作。 > 由于单链表是线性的，使用递归方式将导致栈的使用也是线性的，当链表长度达到一定程度时，递归会导致爆栈，因此，现实中并不推荐使用递归方式来操作链表。 1. 除第一个节点外，递归将链表 reverse 2. 将第一个节点添加到已 reverse 的链表之后 > 这里需要注意的是，每次需要保存已经 reverse 的链表的头节点和尾节点 C++实现 ``` <pre class="calibre18">``` // 普通递归 class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* tail = nullptr; return reverseRecursive(head, tail); } ListNode* reverseRecursive(ListNode *head, ListNode *&tail) { if (head == nullptr) { tail = nullptr; return head; } if (head->next == nullptr) { tail = head; return head; } auto h = reverseRecursive(head->next, tail); if (tail != nullptr) { tail->next = head; tail = head; head->next = nullptr; } return h; } }; // （类似）尾递归 class Solution { public: ListNode* reverseList(ListNode* head) { if (head == nullptr) return head; return reverseRecursive(nullptr, head, head->next); } ListNode* reverseRecursive(ListNode *prev, ListNode *head, ListNode *next) { if (next == nullptr) return head; auto n = next->next; next->next = head; head->next = prev; return reverseRecursive(head, next, n); } }; ``` ``` JavaScript 实现 ``` <pre class="calibre18">``` var reverseList = function (head) { // 递归结束条件 if (head === null || head.next === null) { return head; } // 递归反转子链表 let newReverseList = reverseList(head.next); // 获取原来链表的第 2 个节点 newReverseListTail let newReverseListTail = head.next; // 调整原来头结点和第 2 个节点的指向 newReverseListTail.next = head; head.next = null; // 将调整后的链表返回 return newReverseList; }; ``` ``` Python 实现 ``` <pre class="calibre18">``` class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head ans = self.reverseList(head.next) head.next.next = head head.next = None return ans ``` ``` **复杂度分析** - 时间复杂度：O(N)O(N)O(N) - 空间复杂度：O(N)O(N)O(N) ## 相关题目 - [92.reverse-linked-list-ii](92.reverse-linked-list-ii.html) - [25.reverse-nodes-in-k-groups](25.reverse-nodes-in-k-groups-cn.md) 更多题解可以访问我的LeetCode题解仓库：<https://github.com/azl397985856/leetcode> 。目前已经37K star啦。关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)