206. 反转链表

Difficulty
Medium
Tags
链表
URL
https://leetcode-cn.com/problems/reverse-linked-list/
Star
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
notion imagenotion image
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
notion imagenotion image
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
  • 链表中节点的数目范围是 [0, 5000]
  • 5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
通过次数863,542提交次数1,188,762

法 1 原地翻转

思路
两个指针，第一个指针叫 pre，最初是指向 null 的。 第二个指针 cur 指向 head，然后不断遍历 cur。 每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。 都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。 动画演示如下：
notion imagenotion image
题解
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head

        pre, cur = None, head
        while cur:
            # 临时保存一下 cur 的下一个节点
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp

        return pre

法 2 插入法

思路
按照顺序遍历每个节点，将节点插入到头节点之前
题解
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head

        dummy = ListNode(-1, head)
        cur = head
        while cur.next:
            temp = cur.next
            cur.next = cur.next.next

            temp.next = dummy.next
            dummy.next = temp

        return dummy.next

法 3 递归

思路
把法1原地翻转 改写为 递归版，思路完全一样！！
题解
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        return self.reverse(head=head, pre=None)

    def reverse(self, head, pre):
        if head is None:
            return pre

        temp = head.next
        head.next = pre
        
        pre = head
        head = temp
        return self.reverse(head, pre)