演算專區 Merge Two Sorted Linked Lists

題目

想法

像是 merge sort 的 merge 階段, 用兩個指標, 同時往後走, 每次取比較小的接上去。

可以使用迭代或遞迴的方式, 思路

• 建立一個 dummy 節點 (避免處理頭節點特例)
• 使用 current 指標往後接
• 比較 list1 和 list2 當前節點
• 小的接上
• 移動該 list
• 最後把剩下的整段接上

Java 程式碼

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
	// 建立虛擬節點, 避免處裡頭, null
	​ListNode dummy = new ListNode(-1);
	ListNode current = dummy;
	
	// 當兩邊都還沒走完 
	while (list1 != null && list2 != null) {
		if (lsit1.val <= list2.val) {
			current.next = list1;
			list1 = list1.next;
		}else {
			current.next = list2;
			list2 = list2.next;
		}
		current = current.next;
	}
	
	// 把剩下的接上
	​if (list1 != null) current.next = list1;
	if (list2 != null) current.next = list2;
	
	// dummy 只是輔助節點, 不是答案的一部分
	return dummy.next;
	
}​