206. 反转链表

题目

206. 反转链表（简单）

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

示例 1：

输入：

[1,2,3,4,5]

输出：

[5,4,3,2,1]

示例 2：

输入：

[1,2]

输出：

[2,1]

示例 3：

输入：

[]

输出：

[]

提示：

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

思路

方法一迭代：三指针 prev/curr/nxt，每步先存下后继，再把当前节点的 next 反指向 prev，然后整体右移，遍历结束后 prev 即新头。

方法二递归：先反转 head.next 之后的部分得到 new_head，再让原来的第二个节点指回 head（head.next.next = head），并把 head.next 置空防止成环。

代码

方法一：迭代

# 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: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

方法二：递归

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head