206. Reverse Linked List

Easy

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output:
 [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output:
 [2,1]

Example 3:

Input: head = []
Output:
 []

Constraints:

• The number of nodes in the list is the range [0, 5000].

• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

解題

Runtime: 0 ms, faster than 100%

Memory Usage: 2.9 MB, less than 7.14%

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    arr := make([]int, 0)

    n := head
    for n != nil {
        arr = append(arr, n.Val)
        n = n.Next
    }

    res :=  &ListNode{ }
    cur := res
    for i := len(arr) - 1; i >= 0; i-- {
        cur.Next = &ListNode{ Val:arr[i] }
        cur = cur.Next
    }

    return res.Next
}

二刷

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    stack := make([]*ListNode, 0)

    if head == nil { return nil }

    for head != nil {
        stack = append(stack, head)
        head = head.Next
    }

    for i:=len(stack)-1; i>0; i-- {
        stack[i].Next = stack[i-1]
    }

    stack[0].Next = nil

    return stack[len(stack)-1]
}