25 合并两个排序的链表

牛客

描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

非递归做法

public ListNode Merge(ListNode list1,ListNode list2) {
    if(list1==null) return list2;
    if(list2==null) return list1;
    ListNode head = new ListNode(0);
    ListNode p = head;
    while(true){
        if(list1.val<list2.val){
            p.next = list1;
            list1 = list1.next;
            if(list1 == null){
                p.next.next = list2;
                return head.next;
            }
        } else {
            p.next = list2;
            list2 = list2.next;
            if(list2 == null){
                p.next.next = list1;
                return head.next;
            }
        }
        p = p.next;
    }
}

书上的递归做法。如果节点过多，担心有 stack over flow 的风险。

public ListNode Merge(ListNode list1,ListNode list2) {
    if(list1 == null) return list2;
    if(list2 == null) return list1;
    
    ListNode t = null;
    
    if(list1.val<list2.val){
        t = list1;
        t.next = Merge(list1.next, list2);
    } else {
        t = list2;
        t.next = Merge(list1, list2.next);
    }

    return t;
}