MergeTwoSortedLists [source code]

public class MergeTwoSortedLists {
static
/******************************************************************************/
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0);
        ListNode tail = res;
        while (l1 != null || l2 != null) {
            if (l1 == null || (l1 != null && l2 != null && l2.val <= l1.val)) {
                tail.next = l2;
                ListNode newL2 = l2.next;
                l2.next = null;
                tail = l2;
                l2 = newL2;
            } else {
                tail.next = l1;
                ListNode newL1 = l1.next;
                l1.next = null;
                tail = l1;
                l1 = newL1;
            }
        }
        return res.next;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MergeTwoSortedLists.Solution tester = new MergeTwoSortedLists.Solution();
    }
}

用 LinkedList 的一个好处是, 自动就有末尾判断(注意, 这里的 null 末尾并不是 sentinel 的概念; sentinel 是能够直接参与比较的, 能够直接通过比较来无视是否已经到达 tail);

当出现两个 list 当中有一个提前走完的时候, 有两种处理思路:

直接中止循环, 然后把没有走完的部分直接接到最后的 res 的尾巴上; 这个方法可能你会认为需要再额外单独给 res走一遍, 找到尾巴, 但是这个问题我们以前碰到过了, 只要在最开始的时候, 先用一个指针把尾巴保存下来就行了; 然后最后循环结束的时候, 这个 append 的操作其实就是一个指针操作的事;
在比较的逻辑当中直接嵌入能够处理 null 的逻辑; 我这里选择用这个方式;

刚开始不知道 res 怎么初始化. 事实上这种指针, 也就是 object, 比较好的如果非要初始化, 就直接初始化到 null 就行了;

ListNode res = null;

刚开始第一个 if 前半部分是这么写的:

if (l1 == null || (l1 != null && l1.val <= l2.val)) {  
    head = new ListNode(l2.val);

这样写就很不划算, 因为你这个其实属于重新 allocate 了; 记住, 所有 LinkedList 类的题目, 无论是前面碰到过的删除题目, 转向题目, 还是这里的组合题目, 都有限考虑指针操作;

另外, 这个 if 的 header 也改成了这样: l1 != null && l2 != null 不要怕麻烦,节省冗余逻辑; 虽然我自己也认为不需要判断l2, 但是你这样多加一个冗余逻辑, 一来是避免错误, 二来也让代码的可读性提高了;

最后碰到一个难点, 这个题目刚开始认为只维护 res 就行了,结果最后得到的只能是一个倒过来的 list, 这个肯定是不行的. 为了让每一个 iteration 的新的 head 可以放到 res 这个 list 的末尾, 我们还要维护一个 tail 指针(res 本身是return list的 head, 当然也要留着, 最后返回的就是这个);
然后每一个 iteration 里面, 你维护的基本就是tail, 这个时候发现好像基本上不怎么更新 res 这个 head, 这个就有点问题, 因为 res 跟 tail 之间就没有建立起来联系;
我本来的做法是 res 跟 tail 都是 init 到 Null 的; 那么这个就很尴尬, 两个都是 Null, 是没有办法建立联系的. 一个想到的解决办法就是把两个都 init 到一个 placeholder, 一个实实在在存在的 node, 这样就可以保证, 当我们更新tail.next的时候, 后面的新增加的部分可以跟我们前面的部分保持联系;
最后返回的时候把 res 的第一个 node 扔掉就行了;

最后的速度倒是不怎么理想, 只有17(34). 这个题号是21, 感觉有可能是题目太老的原因, 都知道最优解了;

这个是 submission 最优解: 15(67):

public class Solution {  
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {      
        ListNode res = new ListNode(0);  
        ListNode l3 = res;         

        while(l1!=null && l2!=null){  
            if(l1.val <= l2.val ){  
                l3.next = new ListNode(l1.val);  
                l1 = l1.next;  
            }else{  
                 l3.next = new ListNode(l2.val);  
                l2 = l2.next;  
            }  
            l3 = l3.next;  
        }  

        while(l1!=null){  
              l3.next = new ListNode(l1.val);  
                l1 = l1.next;  
             l3 = l3.next;  
        }  

        while(l2!=null){  
               l3.next = new ListNode(l2.val);  
                l2 = l2.next;  
             l3 = l3.next;  
        }  

        return res.next;  
    }  
}

感觉他这个代码不如我的漂亮, 首先, 他 append 的操作是通过 new 这种 allocate 的操作来完成的, 而不是我的纯粹的指针操作;
不过他比我快的一个原因可能是他采用的是另外一种思路, 就是当两个 list 当中的一个走完的时候, 立刻中止循环. 我刚开始选择另外一种思路的时候是因为一来当时还没有想到指针操作的问题, 二来当时也是想多点思考的乐趣; 不过现在来看, 第一种思路确实要快很多: 极端情况, 假如l1是空的, 我这个就还要专门走一遍 l2, 但是他这个思路就直接一个指针操作就可以结束了;

这个是 discussion 上面看到的一个 recursion 版本的:

class Solution {  
public:  
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {  
        if(l1 == NULL) return l2;  
        if(l2 == NULL) return l1;  

        if(l1->val < l2->val) {  
            l1->next = mergeTwoLists(l1->next, l2);  
            return l1;  
        } else {  
            l2->next = mergeTwoLists(l2->next, l1);  
            return l2;  
        }  
    }  
};

我还是对太熟悉了,完全没有朝 recursion 的方向上面去想, 不过 recursion 来写还是很简练的. 缺点就是这个 recursion 并不是tail-recursion, 所以没有优化, 如果 list 太长, 会 overflow;

评论里面有人提到这么一个问题:
I think everyone forgot about the condition :
Merge two sorted linked lists and return it as "A NEW LIST".

However, the checker did not check for that in this program.

虽然我不认为这个题目考量了这个点, 不过真正面试的时候确实是要考虑一下: 原来的两个 list 是否要求保留; 因为 node 是指针, 所以我们这样把他们全都改了之后, 是会对外面的内存造成影响的;

这个是另外一个版本:

public class Solution {  
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {  
        if(l1 == null || l2 == null ) {  
            return l1 == null ? l2 : l1;  
        }  
        ListNode dummy = new ListNode(0);  
        ListNode current = dummy;  
        while(l1 != null && l2 != null ) {  
            if(l1.val < l2.val ) {  
                current.next = l1;  
                l1 = l1.next;  
            }  
            else {  
                current.next = l2;  
                l2 = l2.next;  
            }  
            current = current.next;  
        }  
        current.next = l1 == null ? l2 : l1;  
        return dummy.next;  
    }  
}

让我想到一个问题, 每次我更新了 tail 之后,我都故意把tail.next在 iteration 结束的位置要保证是 null, 也就是 teardown 掉了,但是仔细想想确实是没有必要的, 因为你下一个 iteration 反正是肯定要更改tail.next的. 就像他这里这样;

另外这个是一个 java 版本的recursion:

public ListNode mergeTwoLists(ListNode l1, ListNode l2){  
        if(l1 == null) return l2;  
        if(l2 == null) return l1;  
        if(l1.val < l2.val){  
            l1.next = mergeTwoLists(l1.next, l2);  
            return l1;  
        } else{  
            l2.next = mergeTwoLists(l1, l2.next);  
            return l2;  
        }  
}

注意 base case 的处理;

另外 disucssion 有人提出一个观点, 就是可以消除dummy head: 只要最开始让 res 跟 tail 都 init 到l1 and l2当中的最小值就可以了, 也就是实际的 head. 这个思路就跟以前把一个 buffer init 到nums[0]是类似的思路, 可以借鉴;

Problem Description

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.

Difficulty:Easy
Category:Algorithms
Acceptance:38.92%
Contributor: LeetCode
Companies
amazon linkedin apple microsoft
Related Topics
linked list
Similar Questions
Merge k Sorted Lists Merge Sorted Array Sort List Shortest Word Distance II

LC21 MergeTwoSortedLists

MergeTwoSortedLists [source code]

Problem Description

results matching ""

No results matching ""