题目描述

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

示例

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

输入：l1 = [], l2 = []
输出：[]

输入：l1 = [], l2 = [0]
输出：[0]

方法一：双指针

题解

这道题目非常简单，可以分为原地与非原地两种情况。

对于非原地合并：使用双指针，每次将较小者加入结果链表即可。需要考虑的是，当一个链表已经到达末尾时，直接将另一链表中的余下结点直接加入即可。

具体实现时的技巧：

定义一个头结点。
对于一个链表已经为空的情况，直接改动结果链表的指针，令其指向非空的链表即可，没必要再一个一个地新建结点并赋值。即部分原地。

对于原地合并：注意修改指针指向时的逻辑，不需要定义新的结点。注意该方法会破坏原有的链表结构，仅适用于原始的两个链表一定不会被需要的情况。

Java代码

以下代码写于2020年1月学习Java时，使用的是非原地合并，并且没有使用上面提到的技巧，仅参考：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    	if(l1==null) return l2;
    	if(l2==null) return l1;
    	ListNode pos1=l1,pos2=l2;
    	ListNode l,curr;
    	if(pos1.val<pos2.val) {
    		l=new ListNode(pos1.val);
    		pos1=pos1.next;
    		curr=l;
    	} else {
    		l=new ListNode(pos2.val);
    		pos2=pos2.next;
    		curr=l;
    	}
    	while(pos1!=null&&pos2!=null) {
        	if(pos1.val<pos2.val) {
        		curr.next=new ListNode(pos1.val);
        		curr=curr.next;
        		pos1=pos1.next;
        	} else {
        		curr.next=new ListNode(pos2.val);
        		pos2=pos2.next;
        		curr=curr.next;
        	}    		
    	}
    	while(pos1!=null) {
        	curr.next=new ListNode(pos1.val);
        	curr=curr.next;
        	pos1=pos1.next;	
    	}
    	while(pos2!=null) {
        	curr.next=new ListNode(pos2.val);
        	curr=curr.next;
        	pos2=pos2.next;	
    	}
    	curr.next=null;
    	return l;
    }
}

Python代码

这里使用原地合并的方法，并且适当使用了一些技巧：

if l1 is not None 可以简写为 if l1
value_1 if judgement else value_2

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        rs_head = ListNode(0)
        r, l1, l2 = rs_head, list1, list2
        while l1 and l2:
            if l1.val < l2.val:
                r.next = l1
                l1 = l1.next
            else:
                r.next = l2
                l2 = l2.next
            r = r.next
        # 考虑余下的一个非空链表
        r.next = l1 if l1 else l2
        # 不返回额外定义的头结点
        return rs_head.next

方法二：递归

题解

我特别喜欢递归，因为会非常考验逻辑，在逻辑正确的情况下，编程会非常简单。

对于该问题的递归，遵循这样一个思路：原地合并，只处理当前的一个结点。分情况讨论当前应该处理哪一个结点，以及终止情况（两个链表中的任一为空）。

Python代码

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2