LeetCode 21. Merge Two Sorted Lists

原题链接在这里：https://leetcode.com/problems/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.

题解：

Method 1:

recursion, stop condition: 一条list 空了，返回另外一条。否则比较两个node value, 取小的，对应的点后移，next 指向用作下次比较返回的结果。

Time Complexity: O(m+n), m 是list1的长度，n 是list2 的长度.

Space: recursion 用的stack的大小, O(m+n).

Method 2:

Iteration, 生成一个dummy, 对应生成currentNode 用来iterate. 每次比较两个点，小的连在current 的后面直到一个为 null, 再把没iterate完的那个连在current后面即可.

Time Complexity: O(m+n).

Space O(1).

AC Java:

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
14         /*
15         //Method 1, Recursion
16         if(l1 == null){
17             return l2;
18         }
19         if(l2 == null){
20             return l1;
21         }
22         
23         ListNode mergeHead;
24         if(l1.val <= l2.val){
25             mergeHead = l1;
26             mergeHead.next = mergeTwoLists(l1.next,l2);
27         }else{
28             mergeHead = l2;
29             mergeHead.next = mergeTwoLists(l1,l2.next);
30         }
31         
32         return mergeHead;
33         */
34         
35         //Method 2, Iteration
36         if(l1 == null){
37             return l2;
38         }
39         if(l2 == null){
40             return l1;
41         }
42         ListNode dummy = new ListNode(0);
43         ListNode current = dummy;
44         while(l1!=null && l2!= null){
45             if(l1.val<=l2.val){
46                 current.next = l1;
47                 l1 = l1.next;
48                 current = current.next;
49             }else{
50                 current.next = l2;
51                 l2 = l2.next;
52                 current = current.next;
53             }
54         }
55         if(l1 != null){
56             current.next = l1;
57         }
58         if(l2 != null){
59             current.next = l2;
60         }
61         return dummy.next;
62     }
63 }

AC JavaScript:

 1 /**
 2  * Definition for singly-linked list.
 3  * function ListNode(val) {
 4  *     this.val = val;
 5  *     this.next = null;
 6  * }
 7  */
 8 /**
 9  * @param {ListNode} l1
10  * @param {ListNode} l2
11  * @return {ListNode}
12  */
13 var mergeTwoLists = function(l1, l2) {
14     var dummy = {
15         val : -1,
16         next : null
17     };
18     
19     var cur = dummy;
20     while(l1 && l2){
21         if(l1.val < l2.val){
22             cur.next = l1;
23             l1 = l1.next;
24         }else{
25             cur.next = l2;
26             l2 = l2.next;
27         }
28         
29         cur = cur.next;
30     }
31     
32     cur.next = l1 || l2;
33     return dummy.next;
34 };

跟上 Merge k Sorted Lists, Merge Sorted Array.