Reverse Linked List

反转链表

题目描述

反转一个链表

示例：

输入：1 -> 2 -> 3 -> 4 -> 5 -> null
输出：5 -> 4 -> 3 -> 2 -> 1 -> null

解法

方法一：递归

• 时间复杂度：O(n)

• 空间复杂度：O(n)

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    p := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return p
}

方法二：迭代

• 时间复杂度：O(n)

• 空间复杂度：O(1)

func reverseList(head *ListNode) *ListNode {
    left := (*ListNode)(nil)
    for head != nil {
        next := head.Next
        head.Next = left
        left = head
        head = next
    }
    return left
}