未分類

Merge Two Sorted Lists

Go, LeetCode, LinkedList, Modify

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

提示 解題應用
LinkedList Pointer

Default:

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

解答思路:

(此題思路有修正，建議看完直接拉到最底下參考修正的部分)

一開始想的是以第一個LinkedList為主(主)，另一個LinkedList(副)就只要將節點依照大小插入主要的LinkedList之中，不過這邊的插入和原先有些出入，原先是真的打算將LinkedList(副)的節點一個一個插入，這樣一來每一個插入LinkedList(主)之後，原先在節點(主)後續銜接的節點又要重新接到新插入節點的後面，而萬一在LinkedList(副)剛好有一長串的節點是要插入同一個節點(主)的後面，就變的相當不自然，因為明明只要將該串(副)的頭、尾節點位置插入節點(主)的前後就可以一口氣塞入整串節點，所以原先的思路上就要以串來想而非單一點。

程式碼解說:

這邊我們主要操作的是第一個LinkedList(主)所以只有這個需要一個頭節點來確保操作上的一致性，另外空節點的情況下預設值是0，因為我們要擺最前面當頭節點要最小，所以要考量到有負數的情況，雖然題目所給的參數不會那麼刁專，其實設個-99就足夠了，不過我這邊還是加了math的package來取得32位元整數的最小值。

1
2
3
4
top := &ListNode{}
top.Val = math.MinInt32
top.Next = l1
l1 = top

首先我以巢狀迴圈來分別讀兩個LinkedList，最外層的迴圈是讀我們主要要操作的LinkedList，所以只有該LinkedList需要記錄前一個節點的位置以方便插入，也因為我們有設頭節頭在前面，所以如果有值要插入原本第一個節點的前面，操作上就和後續的節點一致。內層的迴圈自然就是我們決定要將哪些節點插入至LinkedList(主)中，這邊我是以內層與外層(主LinkedList)比較值的大小，如果內層比外層大就回到外層找下一個節點的值，一直到內層小於外層才插入前一個節點，由此可知插入的判斷是介於 大於目前節點的值 與 小於下一個節 之間，先前提到思路上要以整串節點來插入LinkedList(主)而非以單一節點來一個個插入，這邊我設了一個flag來記錄整串節點的尾巴，同時將符合條件的第一個節點接到LinkedList(主)之後，直到內層比外層的值大才將尾巴也接回LinkedList(主)，而else就是外層主要操作的LinkedList已經到底了，內層卻還有剩的節點，表示其餘的節點都比外層最後且值最小的節點都要來的小，那麼就直接將剩餘的節點直接接上即可，最後有一個例外的狀況是將符合條件的第一個節點接到LinkedList(主)之後，在還沒有出現內層比外層值大的狀況，內層節點就已見底導致flag最後沒有將尾巴接回LinkedList(主)之中，所以在內層迴圈結束之後還要再判斷flag的值是否存在並處理。

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
var tmp *ListNode
var flag *ListNode
for l1 != nil {
	tmp = l1
	l1 = l1.Next
	for l2 != nil {
		if l1 != nil && l1.Val < l2.Val {
			if flag != nil {
				flag.Next = l1
				flag = nil
			}
			break
		} else if l1 != nil && tmp.Val <= l2.Val && l1.Val >= l2.Val {
			if flag == nil {
				tmp.Next = l2
			}
			flag = l2
		} else {
			tmp.Next = l2
			break
		}
		l2 = l2.Next
	}
	if flag != nil {
		flag.Next = l1
		flag = nil
	}
}

完整程式碼:

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
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	top := &ListNode{}
	top.Val = math.MinInt32
	top.Next = l1
	l1 = top
	var tmp *ListNode
	var flag *ListNode
	for l1 != nil {
		tmp = l1
		l1 = l1.Next
		for l2 != nil {
			if l1 != nil && l1.Val < l2.Val {
				if flag != nil {
					flag.Next = l1
					flag = nil
				}
				break
			} else if l1 != nil && tmp.Val <= l2.Val && l1.Val >= l2.Val {
				if flag == nil {
					tmp.Next = l2
				}
				flag = l2
			} else {
				tmp.Next = l2
				break
			}
			l2 = l2.Next
		}
		if flag != nil {
			flag.Next = l1
			flag = nil
		}
	}
	return top.Next
}

總結:

兩排序LinkedList合併成單一LinkedList時，其中做為主來操作，另一則作為輔來當插入點，思路上要以整串節點來插入LinkedList(主)而非以單一節點來一個個插入。

修正:

可以自製一個頭節點來確保開頭節點與其它節點操作上的一致性，並且可以在最後才判斷哪一條的LinkedList已經為nil，最後才將另一條直接接到結果LinkedList的後頭即可

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