021. Merge Two Sorted Lists

难度: Easy

原题连接

• 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.

Example:

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

解题方案

思路 1 **- 时间复杂度: O(N)*- 空间复杂度: O(N)***

代码：

/**
 * 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)***

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

/**
 * 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)***

/**
 * 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;
};

---

我们一直在努力

apachecn/AiLearning

---