题目描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例:

输入:1 -> 2 -> 4 1 -> 3 -> 4

输出:1 -> 1 -> 2 -> 3 -> 4 -> 4

方法 1:递归

思路

 

  • 特殊的,如果 l1 或者 l2 一开始就是 null ,那么没有任何操作需要合并,所以我们只需要返回非空链表。
  • 终止条件:两条链表分别名为 l1 和 l2,当 l1 为空或 l2 为空时结束
  • 返回值:每一层调用都返回排序好的链表头
  • 本级递归内容:如果 l1 的 val 值更小,则将 l1.next 与排序好的链表头相接,l2 同理
  • O),m 为 l1 的长度,n 为 l2 的长度

 

代码实现

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //如果 l1 或者 l2 一开始就是 null ,说明不需要合并,所以我们只需要返回非空链表
        if(l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }
        //如果11的val值更小,则将11.next与排序好的链表头相接,12同理
        if(l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            //每一层调用都返回排序好的链表头
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

 

图解算法

 

 

方法二:迭代

 

思路

我们假设 l1 元素严格比 l2元素少,我们可以将 l2 中的元素逐一插入 l1中正确的位置。

 

  • 首先,我们设定一个哨兵节点 "prehead" ,这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针,我们需要做的是调整它的 next 指针。
  • 然后,我们重复以下过程,直到 l1 或者 l2 指向了 null :如果 l1 当前位置的值小于等于 l2 ,我们就把 l1 的值接在 prev 节点的后面同时将 l1 指针往后移一个。否则,我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面,我们都把 prev 向后移一个元素。
  • 在循环终止的时候, l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的,所以不管哪个链表是非空的,它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面,并返回合并链表。

 

代码实现

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //先初始化一个预先指针 prehead,该指针的下一个节点指向真正的头结点head,是用来定位头结点的
        listnode prehead = new listnode(-1);
        listnode prev = prehead;
        //遍历列表l1和l2,直到全部遍历完毕
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                //prev.next始终指向比较之后的那个小的,l2同理
                prev.next = l1;
                //当前位置的l1后移一位
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        //在循环终止的时候, l1 和 l2 至多有一个是非空的。
        //需要将非空链表接在合并链表的后面,并返回合并链表。
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

 

 

图解算法

 

 

 

 

 

依次类推,最后:

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!