链接： 难度：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;        }    }}