合并链表

合并两个排序的链表

图1

1、递归思路

• 终止条件：两链表其中一个为空时，返回另一个链表；
• 当前递归内容：若list1.val <= list2.val 将较小的list1.next与merge后的表头连接，即list1.next = Merge(list1.next,list2); list2.val较大时同理；
• 每次的返回值：排序好的链表头；

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null){
            return list2;
        }
        else if(list2==null){
            return list1;
        }
        if(list2.val>list1.val){
            list1.next = Merge(list1.next,list2);
            return list1;
        }
        else{
            list2.next = Merge(list1,list2.next);
            return list2;
        }
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

复杂度：时间：O(m+n) 空间： O(m+n)

2、空间O(1)思路

• 创建一个虚拟结点和一个哨兵结点
• 当list1与list2都不为null时循环
• 哪个的val小哪个赋给虚拟结点的next，虚拟结点后移。
• 退出循环后，哪个list不为空，哪个结点（包括剩下的）给虚拟结点的next
• 最后返回哨兵结点的next

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode res = dummy;
        // 必须保证两个list都不为空
        while(list1 != null & list2 != null) {
            if(list1.val > list2.val) {
                dummy.next = list2;
                list2 = list2.next;
                dummy = dummy.next;
            } else if(list1.val <= list2.val) {
                dummy.next = list1;
                list1 = list1.next;
                dummy = dummy.next;
            }
        }
        // list1后面还有，就把剩下的全部拿走
        if(list1 != null) {
            dummy.next = list1;
        }
        if(list2 != null) {
            dummy.next = list2;
        }
        return res.next;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        n_list = ListNode(-1)
        res = n_list

        while list1 and list2:
            if list1.val > list2.val:
                n_list.next = list2
                list2 = list2.next
            else:
                n_list.next = list1
                list1 = list1.next
            n_list = n_list.next

        if list1:
            n_list.next = list1
        if list2:
            n_list.next = list2


        return res.next