forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
143-Reorder-List.go
43 lines (36 loc) · 827 Bytes
/
143-Reorder-List.go
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
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reorderList(head *ListNode) {
slow := head
fast := head.Next
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
reversed := reverse(slow.Next)
slow.Next = nil
curr := head
for curr != nil && reversed != nil {
next := curr.Next
revNext := reversed.Next
curr.Next = reversed
reversed.Next = next
curr = next
reversed = revNext
}
}
func reverse(node *ListNode) *ListNode {
var prev, curr *ListNode = nil, node
for curr != nil {
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev
}