143. Reorder List
題目
題目大意
解題思路
Big O
- 時間複雜 : ``
- 空間複雜 : ``
來源
解答
https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0143.Reorder-List/main.go
package reorderlist
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
// 時間複雜 O(), 空間複雜 O()
// 先用快慢指針找出Linked list的中間點
// 然後把Linked list分成兩半
// 再把後半的Linked list反轉
// 再把兩半的Linked list merge 起來
func reorderList(head *ListNode) {
mid := middleNode(head)
// 2.反轉中間節點的下一個節點
right := resverseNode(mid.Next)
mid.Next = nil
left := head
mergeNode(left, right)
}
// [876. Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/)
func middleNode(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
// [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)
func resverseNode(head *ListNode) *ListNode {
var pre *ListNode
for head != nil {
tmp := head.Next
head.Next = pre
pre = head
head = tmp
}
return pre
}
func mergeNode(l1, l2 *ListNode) {
lcur, rcur := l1, l2
for lcur != nil && rcur != nil {
lcur.Next, rcur.Next, lcur, rcur = rcur, lcur.Next, lcur.Next, rcur.Next
}
}
Benchmark