将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
需要注意的是空节点的处理。
1.暴力
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode prev = dummy; while (l1 != null && l2 != null) { if (l1.val <l2.val ) { prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } prev.next = l1==null? l2 : l1; return dummy.next; }
2.递归
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null) { return l2; } else if (l2 == null) { return l1; } else if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next,l2); return l1; } else { l2.next = mergeTwoLists(l1,l2.next); return l2; } }
