1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58// https://leetcode.com/problems/reverse-linked-list/
package reverselinkedlist
type ListNode struct {
Val int
Next *ListNode
}
func reverseList1(head *ListNode) *ListNode {
var result *ListNode = nil
for current := head; current != nil; current = current.Next {
result = &ListNode{
Val: current.Val,
Next: result,
}
}
return result
}
// time complexity: O(N)
// space complexity: O(N)
func reverseList2(head *ListNode) *ListNode {
newHead, _ := reverseLinkedList(head)
return newHead
}
func reverseLinkedList(head *ListNode) (newHead *ListNode, newTail *ListNode) {
if head == nil || head.Next == nil { // original tail
return head, head
}
newHead, nextNewTail := reverseLinkedList(head.Next)
newTail = head
newTail.Next = nil
nextNewTail.Next = newTail
return
}
// time complexity: O(N)
// space complexity: O(1)
// 但是这种方式会产生递归调用栈，也会消耗空间
// 双指针模式
// time complexity: O(N)
// space complexity: O(1)
func reverseList(head *ListNode) *ListNode {
var previous *ListNode = nil
current := head
for current != nil {
temp := current
current = current.Next
temp.Next = previous
previous = temp
}
return previous
}