未分類

Sort List

Go, LeetCode, LinkedList, Sort

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

提示 解題應用
LinkedList Pointer
Sort MergeSort

Default:

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

解答思路:

要將資料做排序並且要在時間複雜度O(nlogn)之內完成，一開始當然就馬上想到快速排序，不過仔細看題目所給的資料是用LinkedList表示，如果用LinkedList直接硬做快速排序而不使用一些奇淫技巧的話會反而會非常慢，與其要去用那些技巧(像是把LinkedList轉為陣列等等)，倒不如去選擇適合LinkedList的方式，最恰當的當然就是用合併排序的方式來實作，基本上合併排序的概念就是先將資料拆解成細項(每次都將資料拆成兩塊)分別做排序，最後才將已排序的細項兩兩合併回去並再次整理成單一的排序資料，如下圖:

原始資料: [50,10,90,30,70,40,80,60,20]

取自 <<大話資料結構>>

程式碼解說:

合併排序的概念就是先將資料拆解成細項分別做排序才合併回去成單一的排序資料，所以就直接帶入LinkedList至遞回函數來降低流程上的複雜度，其實也算是在解Dynamic Programming的意思

1
2
3
func sortList(head *ListNode) *ListNode {
	return msort(head)
}

再來處理遞回函數的細節，如果該LinkedList為空或只有一個節點便不需要再拆解成兩塊或排序，直接將該節點回傳回去即可，而如果該LinkedList有兩個節點以上，此時便需要將資料拆成兩塊來讓後續能做合併排序，先將LinkedList帶入其它函數以找出中間節點，接著將原LinkedList拆解成左(開頭到中間節點，並記得要將中間節點的下一個位址改成nil)、右(中間節點的下一個到結尾節點)兩塊，最後各別再次帶入遞回函數之中，並且因為拆解後還需兩兩合併回去做排序，所以將剛才兩個拆解的LinkedList遞回函數一起帶入合併函數之後才做回傳

1
2
3
4
5
6
7
8
9
func msort(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	middle := getMiddle(head)
	right := middle.Next
	middle.Next = nil
	return merge(msort(head), msort(right))
}

合併的函數可以先自製一個頭節點來確保開頭節點與其它節點操作上的一致性，同時遍歷兩條LinkedList，如果哪條的開頭節點比較小就將其接到合併的LinkedList後頭(同時紀錄該節點的位置以利後續剩餘節點的嫁接)，並且在最後判斷哪一條的LinkedList已經為nil，才將另一條直接接到結果LinkedList的後頭，待合併結束便回傳自製頭節點的下一個位址(也就是合併排序後新LinkedList開頭節點的位置)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func merge(left *ListNode, right *ListNode) *ListNode {
	header := &ListNode{0, nil}
	pre := header
	for left != nil && right != nil {
		if left.Val < right.Val {
			pre.Next = left
			pre = left
			left = left.Next
		} else {
			pre.Next = right
			pre = right
			right = right.Next
		}
	}
	if left == nil {
		pre.Next = right
	} else {
		pre.Next = left
	}
	return header.Next
}

這邊則是來找出中間節點的位置，同時兩個指標以1:2的速度來遍歷整個LinkedList，當速度比較快的指標到底時(或下一個節點不存在)，此時比較慢的指標會位在中間節點的位置上

1
2
3
4
5
6
7
8
9
10
11
12
func getMiddle(head *ListNode) *ListNode {
	var fast *ListNode
	slow := head
	if head != nil {
		fast = head.Next
	}
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

完整程式碼:

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
44
45
func sortList(head *ListNode) *ListNode {
	return msort(head)
}
func msort(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	middle := getMiddle(head)
	right := middle.Next
	middle.Next = nil
	return merge(msort(head), msort(right))
}
func merge(left *ListNode, right *ListNode) *ListNode {
	header := &ListNode{0, nil}
	pre := header
	for left != nil && right != nil {
		if left.Val < right.Val {
			pre.Next = left
			pre = left
			left = left.Next
		} else {
			pre.Next = right
			pre = right
			right = right.Next
		}
	}
	if left == nil {
		pre.Next = right
	} else {
		pre.Next = left
	}
	return header.Next
}
func getMiddle(head *ListNode) *ListNode {
	var fast *ListNode
	slow := head
	if head != nil {
		fast = head.Next
	}
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

總結:

要將LinkedList做排序並且要在時間複雜度O(nlogn)之內完成，最恰當的方式就是用合併排序的方式來實作，而如果是資料格式是陣列的話反而用快速排序會比較容易。

分享到