21.合并两个有序链表.md

21. 合并两个有序链表

url

题目

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

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

方法

两种方法：递归和迭代

递归：我感觉类似于栈，脑海里可以想象的一个栈，将数据一个一个按照程序存入栈中

• 结束条件，两个，要么是l1为null，要么l2为空
• 如果l1.val < l2.val 则递归，递归l1.next = ??? 谁的值小，谁就递进一步，反之一样。
• 记得返回相应的l1 或者 l2

迭代：非常好理解，安装顺序遍历去对比，不过需要一个中间变量dummy虚拟节点存一下。

code

js

let mergeTwoLists = (l1, 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;
    }
};

go

• 递归

func mergeTwoLists(l1, l2 *ListNode)  *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	if l1.Val < l2.Val {
		l1.Next = mergeTwoLists(l1.Next, l2)
		return l1
	} else {
		l2.Next = mergeTwoLists(l1, l2.Next)
		return l2
	}
}

• 迭代

func mergeTwoLists1(l1, l2 *ListNode)  *ListNode {
	dummy := &ListNode{}
	prev := dummy
	// 迭代的思想
	for l1 != nil && l2 != nil { // 注意条件，二者都不能为nil
		if l1.Val < l2.Val {
			prev.Next = l1
			l1 = l1.Next // 符合，就递进
		} else {
			prev.Next = l2
			l2 = l2.Next // 符合，就递进
		}
		prev = prev.Next // 下一步
	}
	// 剩下单链表
	if l1 != nil {
		prev.Next = l1
	} else {
		prev.Next = l2
	}
	return dummy.Next
}

java

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;
        }
    }
}