LeetCode《初級演算法》連結串列之和並兩個有序連結串列 -- JavaScript

題目

題目連結：http://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnbp2/

題解

順序遍歷，逐個比較

遍歷兩條有序連結串列，比較兩條連結串列的第一個節點的值誰小； 建立一個空的節點（還是有頭節點的連結串列好操作，不用專門考慮第一個節點的處理），將較小值的節點掛載到以建立的空節點為頭節點的連結串列上； 當兩條連結串列中某條連結串列為空時，將另一條連結串列直接掛載到以建立的空節點為頭節點的連結串列上；

```js / * 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) { let head = new ListNode(null,null); let temp = head;

while(l1 !== null && l2 !== null) {

    if(l1.val <= l2.val) {
        temp.next = l1;
        temp = l1;
        l1 = l1.next;
    }else {
        temp.next = l2;
        temp = l2;
        l2 = l2.next;
    }
}

if(l1 !== null) {
    temp.next = l1; 
}

if(l2 !== null) {
    temp.next = l2;
}

return head.next;

};

```

2、遞迴實現

遞迴有時候總會把你繞暈，這個時候結合例項推演一遍能更好的理清演算法；

```js / * 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) {

if(l1 === null){

    return l2;
}else if(l2 === null) {
    return l1;
}

let newHead = null;
if(l1.val <= l2.val) {

    newHead = mergeTwoLists(l1.next,l2);
    // 當遞歸回溯到這裡時，l1.val 和 l2.val 中較大值的節點已經在更深層的遞迴中被連線到了新連結串列中，
    // 接下來將 較小值的節點充當新連結串列的第一個節點，然後返回新連結串列就行了
    l1.next = newHead;
    newHead = l1;

}else {
    newHead = mergeTwoLists(l1,l2.next);
    // 同上
    l2.next = newHead;
    newHead = l2;
}


return newHead;

}; ```

大家如果有更好的思路和解法，歡迎大家一起來討論啊~

這是使用 JavaScript 對 LeetCode《初級演算法》的每道題的總結和實現的其中一篇，彙總篇在這裡：

http://juejin.cn/post/7006692002125316103