ARTS leetcode7 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
           

題目意思：合并兩個有序連結清單，形成一個新的連結清單，合成以後的連結清單也是有序的。

看到這個題的時候，想起了大學上資料結構的時候，學習連結清單知識的第一個例子就是合并兩個有序連結清單，當時是c語言寫的，兩種形式，一種是用遞歸，一種是不用遞歸，我這裡采用了遞歸的方法。

思路：

（1）方法的參數是兩個listNode對象，判斷是否為空，如果全為null,則傳回null，結束；

如果l1為null,則傳回l2;如果l2為null，則傳回l1；

（2）将兩個連結清單的第一個元素做比較，如果l1的第一個節點值小于l2的第一個節點值，那麼就把l1指派給新建立的node對象，

然後node對象的下一個節點就遞歸調用方法，第一個參數就是l1.next，第二個參數l2

（3）将兩個連結清單的第一個元素做比較，如果l1的第一個節點值大于或等于l2的第一個節點值，那麼就把l2指派給新建立的node對象，

然後node對象的下一個節點就遞歸調用方法，第一個參數就是l1，第二個參數l2.next

舉個例子來說一下，(2)(3)中傳參的含義：就用上面的demo來說，1和1相比較，走(3)，l2的第一個被指派到node，然後我們需要做的就是将l2的next然後繼續與l1的一個相比較，是以傳參就是這個意思。

代碼實作（遞歸形式）:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       ListNode node;
        if(l1 == null && l2 == null){
            return null;
        }
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        if(l1.val<l2.val){
            node = l1;
            node.next = mergeTwoLists(l1.next,l2);
        }else {
            node = l2;
             node.next = mergeTwoLists(l1,l2.next);
        }
        return node;
    }
}
           

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Two Sorted Lists.
Memory Usage: 37 MB, less than 97.90% of Java online submissions for Merge Two Sorted Lists.
           

code2:非遞歸的形式，利用循環，代碼實作如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null && l2 == null){
            return null;
        }
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        //首先的初始化一個node
        ListNode result = new ListNode(0);
        ListNode node = result;
        //兩個node都不為空的情況下循環
        while(l1!=null && l2!=null){
            if(l1.val<l2.val){
                node.next = l1;
                l1 = l1.next;
            }else {
                node.next = l2;
                 l2 = l2.next;
            }
            node = node.next;
        }
        //這裡主要是為了兩個連結清單長度不一樣的時候，所采取的處理方法。
        if(l1!=null){
            node.next = l1;
        }
        if(l2!=null){
            node.next = l2;
        }
        //因為初始化的時候給連結清單多一個節點0，是以隻需要0以後的節點就ok
        return result.next;
    }
}
           

Runtime: 1 ms, faster than 99.55% of Java online submissions for Merge Two Sorted Lists.
Memory Usage: 36.8 MB, less than 98.00% of Java online submissions for Merge Two Sorted Lists.
           

繼續看另外一種實作，是在leetcode discuss中看到的一個大佬寫的，代碼實作很簡潔，并沒有建立新的ListNode對象，但是他缺了一種考慮，就是如果兩個連結清單都是空的情況下，應該傳回null(個人了解)。他也采用了遞歸的形式進行調用，但是存在一個問題，題目說了需要傳回一個new List來存儲合并後的list的值，但是這個大佬的寫法是改變了原有連結清單的值，在沒有重新建立list的情況下，也實作了，感覺和題目要求有點背離，但是居然也跑成功了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    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(l1, l2.next);
			return l2;
		}
    }
}
           

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Two Sorted Lists.
Memory Usage: 37.1 MB, less than 97.90% of Java online submissions for Merge Two Sorted Lists.