21. [E] Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

递归,需要遍历两个链表的所有节点,因此复杂度 O(m+n)

class Solution {
public ListNode mergeTwoLists(ListNode a, ListNode b) {
if (a == null) {
return b;
}
if (b == null) {
return a;
}
if (a.val < b.val) {
a.next = mergeTwoLists(a.next, b);
return a;
} else {
b.next = mergeTwoLists(a, b.next);
return b;
}
}
}

循环,只需要遍历到最短的那一条链表,所以复杂度 O(min(m, n))

class Solution {
public ListNode mergeTwoLists(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0);
ListNode head = dummy;
while (a != null && b != null) {
if (a.val < b.val) {
head.next = a;
a = a.next;
} else {
head.next = b;
b = b.next;
}
head = head.next;
}
if (a != null) {
head.next = a;
} else {
head.next = b;
}
return dummy.next;
}
}