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.
Solution1：Iterative遍歷
思路：持續(xù)遍歷比較霹俺，將小的relink到新的結(jié)果list编曼。最后將多余的link一下
Time Complexity: O(N) Space Complexity: O(1)
Solution2：Recursive：先序處理
思路：發(fā)現(xiàn)pattern子問(wèn)題求橄，處理好當(dāng)前的函卒，遞歸剩下的
Time Complexity: O(N) Space Complexity: O(N) 遞歸緩存
Solution1 Code：
class Solution1 {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode cur1 = l1;
ListNode cur2 = l2;
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while(cur1 != null && cur2 != null) {
if(cur1.val < cur2.val) {
cur.next = cur1;
cur1 = cur1.next;
}
else {
cur.next = cur2;
cur2 = cur2.next;
}
cur = cur.next;
}
// the rest
cur.next = cur1 == null ? cur2 : cur1;
return dummy.next;
}
}
Solution2 Code：
class Solution2 {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l2.next, l1);
return l2;
}
}
}
