143. Reorder List

題目

題目大意

解題思路

Big O

• 時間複雜 : ``
• 空間複雜 : ``

來源

• https://leetcode.com/problems/reorder-list/description/
• https://leetcode.cn/problems/

解答

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