[LeetCode] Merge Two Sorted Lists 合并两个排好序的链表

链接： https://leetcode.com/problems/merge-two-sorted-lists/#/description
难度：Easy
题目：21. 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.
翻译：合并两个排好序的链列，并将其作为新链表返回。新链表应通过将前两个列表的节点拼接在一起。
思路一：新建一个头指针指向0的临时链表，比较l1和l2的当前值的大小，把临时链表的next节点指向较小的节点，l1或者l2的指针后移一位，依次往下，直到l1或者l2为空，则把临时链表的next节点指向最后那段非空的链表，返回临时链表的第二个节点（头一个节点为0）。
参考代码一（Java）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newList = new ListNode(0);
        ListNode nextList = newList;
        
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                nextList.next = l1;
                l1 = l1.next;
            }else{
                nextList.next = l2;
                l2 = l2.next;
            }
            nextList = nextList.next;
        }
        
        if(l1 != null){
            nextList.next = l1;
        }else{
            nextList.next = l2;
        }
        
        return newList.next;
            
    }
}

思路二：使用递归法。构造一个临时链表，当l1当前节点的值大于l2当前节点的值时，我们把l2这个较小的值赋给临时链表的下一个节点，并将l2的下一个节点的值和l1当前节点的值放到下一次做对比，依次递归下去。
参考代码二（Java）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val > l2.val) {
            ListNode tmp = l2;
            tmp.next = mergeTwoLists(l1, l2.next);
            return tmp;
        } else {
            ListNode tmp = l1;
            tmp.next = mergeTwoLists(l1.next, l2);
            return tmp;
        }
    }
}