206. 反转链表

题目

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

示例 1:

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

输出：[5,4,3,2,1]

示例 2:

输入：head = [1,2]

输出：[2,1]

复杂度

虚拟头结点

• 时间复杂度：\(O(n)\)
• 空间复杂度：\(O(1)\)

题解

Go

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr != nil {
        nxt := curr.Next // 保存 curr.next
        curr.Next = prev
        prev = curr
        curr = nxt
    }
    return prev
}

Python

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            nxt = curr.next   # 保存 curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev