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