README.md

title	subtitle	date	lastmod	draft	author	authorLink	description	license	images	tags	categories	featuredImage	featuredImagePreview	hiddenFromHomePage	hiddenFromSearch	twemoji	lightgallery	ruby	fraction	fontawesome	linkToMarkdown	rssFullText	toc	code	math	mapbox	share	comment	library	seo
143. Reorder List	https://leetcode.com/problems/reorder-list/description/	2024-03-03 16:53:00 +0800	2024-03-03 16:53:00 +0800	false	Kimi.Tsai	https://kimi0230.github.io/	0143.Reorder-List			LeetCode Go /Medium 143. Reorder List Amazon Microsoft Adobe Facebook Bloomberg Linked List Two Pointers Stack Recursion	LeetCode			false	false	false	true	true	true	true	false	false	enable auto true true	copy maxShownLines true 200	enable		enable true	enable true	css js	images

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