206. Reverse Linked List

題目

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?

題目大意

將 Linked List 反向

解題思路

來源

• https://leetcode.com/problems/Reverse Linked List/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0000.kkkk/main.go

package reverselinkedlist

import (
    . "LeetcodeGolang/structures"
)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func ReverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    var prev *ListNode

    for head != nil {
        next := head.Next
        head.Next = prev
        prev = head
        head = next
    }

    return prev
}

func ReverseListRecursively(head *ListNode) *ListNode {
    return ListRecursivelyChild(head, nil)
}

func ListRecursivelyChild(current *ListNode, prev *ListNode) *ListNode {
    if current == nil {
        return prev
    }
    next := current.Next
    current.Next = prev
    return ListRecursivelyChild(next, current)
}

Benchmark

goos: darwin
goarch: amd64
pkg: LeetcodeGolang/Leetcode/0206.Reverse-Linked-List
cpu: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
BenchmarkReverseList-8                  1000000000               0.7960 ns/op          0 B/op          0 allocs/op
BenchmarkReverseListRecursively-8       276534334                4.374 ns/op           0 B/op          0 allocs/op
PASS
ok      LeetcodeGolang/Leetcode/0206.Reverse-Linked-List        2.597s