[Leetcode 44]合并有序列表Merge k Sorted Lists

【题目】

将两个有序链表合并成一个有序链表

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

 

Example 1:

[Leetcode 44]合并有序列表Merge k Sorted Lists

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: l1 = [], l2 = []
Output: []

Example 3:

Input: l1 = [], l2 = [0]
Output: [0]

 

【思路】

是把l1/l2的next指针向着对方或者自己的next相连

 

 

 

要想清楚为什么return L1/L2,他俩就能连一起,得到最终结果

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

L1<L2时,l1.next=l2, 连后主动权在l1,返回l1

L1>L2时,l2.next=l1,  连后主动权在l2,返回l2

============

虽然是个简单题但之前大晚上脑袋瓦特想歪了……错误思路也记下

L1<L2时,l1.next=l2, 返回l1

L1>L2时,l2.next=l2.next, 返回l2

看上去在分别处理,互不干扰死循环??

醒醒,写成下面这样才叫互不干扰……上面其中一个指针动了,另一个没动,动了的指针就连到没动那了

l1.next= mergeTwoLists(l1.next,l2.next);
l2.next= mergeTwoLists(l1.next,l2.next);

 

【代码】

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(l1,l2.next);
            return l2;
        }
    }
}

Q:为什么其中一个为null,就返回另一个?

A:因为是有序的,另一个剩余部分也是有序的,不用再遍历。

 

Q:为什么返回的另一个里就一定是结果?这里l1 l2代表的到底是什么,为什么是整串数而不是一部分

A:倒推,合并后的数列长度一定更长。那剩到最后返回的肯定是更长的。



上一篇:转载:《44个Javascript变态题》


下一篇:8个免费实用的C++GUI库(转载)