最后一遍-L21-Merge Two Sorted Lists
You are given the heads of two **sorted** linked lists list1 and list2.
Merge the two lists in a one **sorted** list.
The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
Constraints:
* The number of nodes in both lists is in the range [0, 50].
* -100 <= Node.val <= 100
* Both list1 and list2 are sorted in non-decreasing order.
NOTE:经典数据结构链表的合并问题
class Solution {
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode curL1 = l1;
ListNode curL2 = l2;
ListNode cur= new ListNode(0);
ListNode head = cur;
while(curL1 != null || curL2 != null){
if(curL1 == null){
cur.next= curL2;
break;
}else if(curL2 == null){
cur.next = curL1;
break;
}else {
if(curL1.val < curL2.val){
cur.next = curL1;
curL1 = curL1.next;
cur = cur.next;
}else {
cur.next = curL2;
curL2 = curL2.next;
cur = cur.next;
}
}
}
return head.next;
}
}
另外的一种解法：
class Solution{
/**
* 递归的写法，比较的别致
*/
public ListNode mergeTwoLists_iterator(ListNode l1, ListNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists_iterator(l1.next, l2);
return l1;
} else{
l2.next = mergeTwoLists_iterator(l1, l2.next);
return l2;
}
}
}