0021._Merge_Two_Sorted_Lists

发表于 分类于 ， ，

021. Merge Two Sorted Lists

难度: Easy

原题连接

内容描述

1
2
3
4
5
6
7
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
**- 时间复杂度: O(N)**- 空间复杂度: O(N)**

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    if(l2 == null) return l1;
    if(l1 == null) return l2;
    if(l1.val<l2.val){
        l1.next = mergeTwoLists(l1.next,l2);
        return l1;
    }else{
        l2.next = mergeTwoLists(l2.next,l1);
        return l2;
    }
};

思路 2: 暴力解法
**- 时间复杂度: O(2N)**- 空间复杂度: O(2N)**

由于是有序的链表，所以可以用数组中转的方式。把两个数组全部转成数组，再将两个数组合并再排序，最后再将两个数组转化为链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
  if (!l1 && !l2) {
    return null
  }
  let array1 = listNodeToArray(l1)
  let array2 = listNodeToArray(l2)
  let array = array1.concat(array2)
  array.sort((a, b) => (a - b))
  
  return arrayToListNode(array)
};


function listNodeToArray (head) {
  let array = []
  while (head) {
    array.push(head.val)
    head = head.next
  }
  return array
}

function arrayToListNode(array) {
  if(!array || !array.length) {
    return null
  }
  
  let node
  let head = new ListNode(array[0])
  let pnode = head
  
  for(let i = 1; i < array.length; i++) {
    node = new ListNode(array[i])
    pnode.next = node
    pnode = node
  }
  
  return head
}

思路 3: 单次循环遍历
**- 时间复杂度: O(N)**- 空间复杂度: O(N)**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
let mergeTwoLists = function(l1, l2) {
    if(!l1 || !l2){
        return (l1 || l2)
    }
    let result = new ListNode;
    let preNode = result;
    while (l1 || l2){
        let currentNode = new ListNode;
        if(!l2){
            currentNode.val = l1.val;
            l1 = l1.next;
        }else if(!l1){
            currentNode.val = l2.val;
            l2 = l2.next;
        }else{
            if(l1.val < l2.val){
                currentNode.val = l1.val;
                l1 = l1.next;
            }else{
                currentNode.val = l2.val;
                l2 = l2.next;
            }
        }
        preNode.next = currentNode;
        preNode = currentNode;
    }
    return result.next;
};