未分類

Insertion Sort List

Go, LeetCode, LinkedList, Sort

Insertion Sort List

Sort a linked list using insertion sort.

提示 解題應用
LinkedList Pointer
Sort Insertion Sort

Default:

1
2
3
4
5
6
7
8
9
10
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func insertionSortList(head *ListNode) *ListNode {
}

解答思路:

這題要你實作LinkedList的插入排序，只要有玩過撲克牌的人都應該有整理排的經驗，如果卡片比前面的牌小就抽出該張卡往前面找，直到發現前面已排序的卡片有大小範圍最接近該張卡片的位置才做插入，不過因為是單向的LinkedList，所以在抽出節點之後是從最開頭向後找直到發現比該值大的節點才插在前面。

程式碼解說:

為了確保能一直指向LinkedList最新的開頭節點(也能讓開頭節點與其它節點一樣有操作上的一致性)，一開始便自行製做一個頭節點並將LinkedList接在頭節點後頭才開始遍歷，每次比較就像是整理撲克牌一樣，如果節點值比前面的小就抽出該節點，而因為前面經整理後都會是由小排序至大的LinkedList，所以其實前一個節點都會是到該節點為止的最大值，如果目前遍歷到的節點值比最大值大，便將該節點值取代最大值並繼續往下遍歷(也要記得記錄前一個節點的位置以利後續發生要嫁接的情況)，如果遍歷到的節點值比最大值小，這時就需要將節點抽出(這邊是將抽出節點的前一個與下一個節點做嫁接)，並找出前面已排序LinkedList的適當位置做插入(這邊帶入頭節點與該節點的位置至其它函數處理)，待LinkedList排序完畢之後便回傳自製頭節點的下一個位址(也就是排序LinkedList最新的開頭節點)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func insertionSortList(head *ListNode) *ListNode {
	var next *ListNode
	header := &ListNode{0, head}
	pre := header
	max := math.MinInt32
	for head != nil {
		next = head.Next
		if head.Val >= max {
			max = head.Val
			pre = head
		} else {
			pre.Next = head.Next
			insert(header, head)
		}
		head = next
	}
	return header.Next
}

這邊則是處理抽出來的節點所要插入的位置，先以一迴圈從頭開始遍歷節點，如果發現比抽出節點值大的節點，就將抽出的節點嫁接在較大節點值的前一個與該節點之間並結束迴圈

1
2
3
4
5
6
7
8
9
10
11
12
13
func insert(header *ListNode, node *ListNode) {
	pre := header
	head := header.Next
	for head != nil {
		if node.Val < head.Val {
			pre.Next = node
			node.Next = head
			break
		}
		pre = head
		head = head.Next
	}
}

完整程式碼:

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
func insertionSortList(head *ListNode) *ListNode {
	var next *ListNode
	header := &ListNode{0, head}
	pre := header
	max := math.MinInt32
	for head != nil {
		next = head.Next
		if head.Val >= max {
			max = head.Val
			pre = head
		} else {
			pre.Next = head.Next
			insert(header, head)
		}
		head = next
	}
	return header.Next
}
func insert(header *ListNode, node *ListNode) {
	pre := header
	head := header.Next
	for head != nil {
		if node.Val < head.Val {
			pre.Next = node
			node.Next = head
			break
		}
		pre = head
		head = head.Next
	}
}

總結:

要實作LinkedList的插入排序其實就像整理撲克牌一樣，卡片比前面的牌小就抽出該張卡往前面找適當的位置，而如果是單向的LinkedList，在抽出節點之後要從最開頭向後找直到發現比該值大的節點才插在前面。

分享到