题目要求

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