381，合并两个有序链表（易）

Correction does much, but encouragement does more. 

纠正很有用，但鼓励的作用更大。

问题描述

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

示例：

输入：1->2->4, 1->3->4

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

问题分析

这题比较简单，因为链表是升序的，我们只需要遍历每个链表的头，比较一下哪个小就把哪个链表的头拿出来放到新的链表中，一直这样循环，直到有一个链表为空，然后我们再把另一个不为空的链表挂到新的链表中。我们就以3→4→7→9和2→5→6两个链表来画个图看一下是怎么合并的。

01链表合并代码

 1public ListNode mergeTwoLists(ListNode linked1, ListNode linked2) {
 2    //下面4行是空判断
 3    if (linked1 == null)
 4        return linked2;
 5    if (linked2 == null)
 6        return linked1;
 7    ListNode dummy = new ListNode(0);
 8    ListNode curr = dummy;
 9    while (linked1 != null && linked2 != null) {
10        //比较一下，哪个小就把哪个放到新的链表中
11        if (linked1.val <= linked2.val) {
12            curr.next = linked1;
13            linked1 = linked1.next;
14        } else {
15            curr.next = linked2;
16            linked2 = linked2.next;
17        }
18        curr = curr.next;
19    }
20    //然后把那个不为空的链表挂到新的链表中
21    curr.next = linked1 == null ? linked2 : linked1;
22    return dummy.next;
23}

02链表合并递归写法

 1public ListNode mergeTwoLists(ListNode linked1, ListNode linked2) {
 2    if (linked1 == null)
 3        return linked2;
 4    if (linked2 == null)
 5        return linked1;
 6    if (linked1.val < linked2.val) {
 7        linked1.next = mergeTwoLists(linked1.next, linked2);
 8        return linked1;
 9    } else {
10        linked2.next = mergeTwoLists(linked1, linked2.next);
11        return linked2;
12    }
13}

递归写法其实我们还可以写的更简洁一些

1public ListNode mergeTwoLists(ListNode linked1, ListNode linked2) {
2    //只要有一个为空，就返回另一个
3    if (linked1 == null || linked2 == null)
4        return linked2 == null ? linked1 : linked2;
5    //把小的赋值给first
6    ListNode first = (linked2.val < linked1.val) ? linked2 : linked1;
7    first.next = mergeTwoLists(first.next, first == linked1 ? linked2 : linked1);
8    return first;
9}

长按上图，识别图中二维码之后即可关注。

如果喜欢这篇文章就点个"在看"吧