# 0206. 反转链表

### 题目地址(206. 反转链表)

<https://leetcode-cn.com/problems/reverse-linked-list/>

### 题目描述

反转一个单链表。

```
示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

```

### 前置知识

* [链表](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/basic-data-structure)

### 公司

* 阿里
* 百度
* 腾讯
* adobe
* amazon
* apple
* bloomberg
* facebook
* microsoft
* snapchat
* twitter
* uber
* yahoo
* yelp
* zenefits

### 思路

这个就是常规操作了，使用一个变量记录前驱 pre，一个变量记录后继 next，不断更新`current.next = pre` 就好了。

链表的题目 90% 的 bug 都出现在：

1. 头尾节点的处理
2. 指针循环引用导致死循环

因此大家对这两个问题要保持 100% 的警惕。

### 关键点解析

* 链表的基本操作（交换）
* 虚拟节点 dummy 简化操作
* 注意更新 current 和 pre 的位置， 否则有可能出现溢出

### 代码

语言支持：JS, C++, Python,Java

JavaScript Code：

```js
/**
 * 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：

```
/**
 * 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:

```python
# 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:

```java
/**
 * 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(1)$

### 拓展

通过单链表的定义可以得知，单链表也是递归结构，因此，也可以使用递归的方式来进行 reverse 操作。

> 由于单链表是线性的，使用递归方式将导致栈的使用也是线性的，当链表长度达到一定程度时，递归会导致爆栈，因此，现实中并不推荐使用递归方式来操作链表。

1. 除第一个节点外，递归将链表 reverse
2. 将第一个节点添加到已 reverse 的链表之后

> 这里需要注意的是，每次需要保存已经 reverse 的链表的头节点和尾节点

C++实现

```
// 普通递归
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 实现

```javascript
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 实现

```python
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)$

### 相关题目

* [92.reverse-linked-list-ii](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/92.reverse-linked-list-ii)
* [25.reverse-nodes-in-k-groups](https://github.com/azl397985856/leetcode/blob/master/problems/25.reverse-nodes-in-k-groups-cn.md)

更多题解可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/in5o20.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/206.reverse-linked-list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.