Leetcode: Merge Two Sorted Lists

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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

方法二（推荐方法1）：

新的Linkedlist不以任何现有List为依托，维护一个dummmy node和当前节点ListNode cur，把两个list的元素往里面插入作为cur.next，每次不new一个新的ListNode, 而是用已有的。相较于法一最后需要讨论两个list各自没有走完的情况

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 class Solution {
10     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
11         ListNode dummy = new ListNode(-1);
12         ListNode cur = dummy;
13         while (l1 != null && l2 != null) {
14             if (l1.val <= l2.val) {
15                 cur.next = l1;
16                 l1 = l1.next;
17             }
18             else {
19                 cur.next = l2;
20                 l2 = l2.next;
21             }
22             cur = cur.next;
23         }
24         cur.next = l1 != null ? l1 : l2;
25         return dummy.next;
26     }
27 }

方法三：（推荐方法2）Recursion

 1 public ListNode mergeTwoLists(ListNode l1, ListNode l2){
 2         if(l1 == null) return l2;
 3         if(l2 == null) return l1;
 4         if(l1.val < l2.val){
 5             l1.next = mergeTwoLists(l1.next, l2);
 6             return l1;
 7         } else{
 8             l2.next = mergeTwoLists(l1, l2.next);
 9             return l2;
10         }
11 }