21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
链表解题经典三把斧：
- 哑巴节点
- 栈
- 快慢指针
此题比较容易想到的解法是迭代法，生成哑巴节点，然后迭代生成后续节点。
方法一、迭代法
Swift
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
guard list1 != nil else {
return list2
}
guard list2 != nil else {
return list1
}
var list1 = list1
var list2 = list2
let dummyNode = ListNode(-1);
var prev:ListNode? = dummyNode
while list1 != nil && list2 != nil {
if list1!.val < list2!.val {
prev?.next = list1
list1 = list1!.next
}else {
prev?.next = list2
list2 = list2!.next
}
prev = prev?.next
}
prev?.next = (list1 != nil) ? list1 : list2
return dummyNode.next
}
OC
//回溯法
- (ListNodeOC *_Nullable)mergeTwoLists:(ListNodeOC * _Nullable)list1
list2:(ListNodeOC * _Nullable)list2 {
if (!list1) {
return list2;
}
if (!list2) {
return list1;
}
ListNodeOC *dummyNode = [[ListNodeOC alloc] initWithVal:-1];
ListNodeOC *pre = dummyNode;
while (list1 && list2) {
if (list1.val < list2.val) {
pre.next = list1;
list1 = list1.next;
}else {
pre.next = list2;
list2 = list2.next;
}
pre = pre.next;
}
pre.next = list1 ? list1 : list2;
return dummyNode.next;
}
方法二、递归法
代码简洁、思路清晰、稍占内存的解法。
Swift
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
guard let list1 = list1 else {
return list2 }
guard let list2 = list2 else {
return list1 }
if list1.val < list2.val {
list1.next = mergeTwoLists(list1.next, list2)
return list1
}else {
list2.next = mergeTwoLists(list1, list2.next)
return list2
}
}
OC
//递归法
- (ListNodeOC * _Nullable)mergeTwoLists:(ListNodeOC * _Nullable)list1
list2:(ListNodeOC * _Nullable)list2 {
//递归终止条件
if (!list1) {
return list2;
}
if (!list2) {
return list1;
}
if (list1.val < list2.val) {
list1.next = [self mergeTwoLists:list1.next list2:list2];
return list1;
}else {
list2.next = [self mergeTwoLists:list1 list2:list2.next];
return list2;
}
}
