leetcode21.Merge Two Sorted Lists

题目要求

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

翻译过来就是：将两个有序的链表组合成一个新的有序的链表

思路一：循环

在当前两个链表的节点都是非空的情况下比较大小，较小的添入结果链表中并且获得较小节点的下一个节点。这样比较直至至少遍历完一个链表。再将剩下的链表添至结果链表的末端

public class MergeTwoSortedLists_21 {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode start = new ListNode(0);
        ListNode temp = new ListNode(0);
        start.next = temp;
        while(l1!=null && l2!=null){
            if(l1.val <= l2.val){
                temp.next = l1;
                l1 = l1.next;
            }else{
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }
        if(l1!=null){
            temp.next = l1;
        }
        if(l2!=null){
            temp.next = l2;
        }
        return start.next.next;
    }
    
    public class ListNode{
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}

思路二：递归

每次比较得到两个节点中较小的节点作为结果返回，并继续对剩下来的链表重新获得较小节点。

public class MergeTwoSortedLists_21 {
    public ListNode mergeTwoLists_recursive(ListNode l1, ListNode l2){
        if(l1==null){
            return l2;
        }else if (l2==null){
            return l1;
        }
        ListNode mergeHead;
        if(l1.val <= l2.val){
            mergeHead = l1;
            mergeHead.next = mergeTwoLists_recursive(l1.next, l2);
        }else{
            mergeHead = l2;
            mergeHead.next = mergeTwoLists(l1, l2.next);
        }
        return mergeHead;
    }
    
    public class ListNode{
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}