原文链接: https://leetcode-cn.com/problems/UHnkqh

中文题目

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

 

示例 1：

复制

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

示例 2：

复制

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

示例 3：

复制

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

 

提示：

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

 

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

 

注意：本题与主站 206 题相同： https://leetcode-cn.com/problems/reverse-linked-list/

通过代码

高赞题解

1. 迭代解法

请看视频：

206_1_迭代解法.mp4

代码如下：

复制

[]
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

复制

[]
public:
    ListNode* reverseList1(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

复制

[]
def reverseList(self, head: ListNode) -> ListNode:
    prev, curr = None, head
    while curr is not None:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    return prev

复制

[]
var reverseList = function(head) {
    let prev = null, curr = head
    while (curr) {
        const next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    return prev
};

复制

[]
// 迭代
func reverseList1(head *ListNode) *ListNode {
    var prev *ListNode = nil
    var curr = head
    for curr != nil {
        var next = curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }
    return prev
}

2. 递归解法

2.1 为什么可以使用递归

请看视频：

...06_2_为什么可以使用递归实现.mp4

2.2 递归解法思路

请看视频：

206_3_递归实现.mp4

代码如下：

复制

[]
public ListNode reverseList(ListNode head) {
    // 1. 递归终止条件
    if (head == null || head.next == null) {
        return head;
    }
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

复制

[]
public:
    ListNode* reverseList(ListNode* head) {
        // 1. 递归终止条件
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* p = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return p;
    }

复制

[]
def reverseList(self, head: ListNode) -> ListNode:
    # 1. 递归终止条件
    if head is None or head.next is None:
        return head
    
    p = self.reverseList(head.next)
    head.next.next = head
    head.next = None

    return p

复制

[]
var reverseList = function(head) {
    // 1. 递归终止条件
    if (head == null || head.next == null) return head
    const p = reverseList(head.next)
    head.next.next = head
    head.next = null
    return p
};

复制

[]
// 递归
func reverseList(head *ListNode) *ListNode {
    // 1. 递归终止条件
    if head == nil || head.Next == nil {
        return head
    }
    var p = reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return p
}

在刷题的时候：

1. 如果你觉得自己数据结构与算法基础不够扎实，那么请点这里，这里包含了一个程序员 5 年内需要的所有算法知识。

2. 如果你感觉刷题太慢，或者感觉很困难，或者赶时间，那么请点这里。这里用 365 道高频算法题，带你融会贯通算法知识，做到以不变应万变。

3. 回溯、贪心和动态规划，是算法面试中的三大难点内容，如果你只是想搞懂这三大难点内容 请点这里。

以上三个链接中的内容，都支持 Java/C++/Python/js/go 五种语言

统计信息

通过次数	提交次数	AC比率
18829	24594	76.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言