21.合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists

解法有两种：

1.递归思路

​ 思路很简单，递归首先要考虑边界情况，也就是什么时候停止。当l1走到空时，返回的一定是l2，l2空时同理。

​ 当l1较小时，l1为头节点，返回的肯定是l1，再跳转到l1.next进行递归。l2小时同理。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.迭代思路
设置一个哨兵节点（prehead），这个结点用来返回值，再来一个指针节点（pre）用来遍历两个链表。设置指针节点等于哨兵节点（这点很重要），比较l1和l2大小，判断头节点，让pre.next指向（此时哨兵节点也指向了头节点）。再遍历链表。

class Solution {
	    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
	    	ListNode prehead = new ListNode(-1);
	    	ListNode pre = prehead;
	    	while(l1 != null && l2 != null) {
	    		if(l1.val <= l2.val) {
	    			pre.next = l1;
	    			l1 = l1.next;
	    		}else {
	    			pre.next = l2;
	    			l2 = l2.next;
	    		}
	    		pre = pre.next;
	    	}
	    	pre.next = l1 == null ? l2 : l1;
	    	return prehead.next;
	    }
}

这个解法不用判断是否为空，因为返回的是prehead.next。