合并兩個有序連結清單
題目描述
将兩個升序連結清單合并為一個新的 升序 連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。
示例 1:
輸入:l1 = [1,2,4], l2 = [1,3,4]
輸出:[1,1,2,3,4,4]
示例 2:
輸入:l1 = [], l2 = []
輸出:[]
示例 3:
輸入:l1 = [], l2 = [0]
輸出:[0]
思路
建立一個連結清單,作為傳回結果,用指針周遊兩個連結清單,比較兩個連結清單的目前節點,将較小的先接入新連結清單,并将指針後移。
題解
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function(l1, l2) {
//建立連結清單,ListNode 題目提供
let result = new ListNode(0);
let p = result, p1 = l1, p2 = l2;
while(p1 && p2){
if(p1.val < p2.val){
p.next = p1;
p1 = p1.next
}
else{
p.next = p2;
p2 = p2.next;
}
//指針後移
p = p.next;
}
if(p1) p.next = p1;
if(p2) p.next = p2;
//傳回時去除建立連結清單時的 0
return result.next;
}