LeetCode 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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
解析：
将两个有序链表合并成为一个
思路：首先判断两个链表是否为空，如果l1为空则返回L2，反之亦然。定义新链表的头结点，一次遍历l1和l2，比较大小，选择二者中较小的付给新的链表节点，然后依次后移，遍历完成之后判断l1和l2是否为空，如果不为空则直接把剩余链表赋值给新链表。
代码1 非递归

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
    public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL)//l1为空则返回l2
            return l2; 
        else if(l2 == NULL)
            return l1;
        ListNode* head = new ListNode(-1);
        //头结点
        ListNode * temp = head;
        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;  
        else
            temp->next = l2;
        return head->next;
    }
};

代码2 递归方式
当某个链表为空了，就返回另一个。核心还是比较当前两个节点值大小，如果l1的小，那么对于l1的下一个节点和l2调用递归函数，将返回值赋值给l1.next，然后返回l1；否则就对于l2的下一个节点和l1调用递归函数，将返回值赋值给l2.next，然后返回l2。

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if(l1 == NULL)
        return l2; 
        else if(l2 == NULL)
        return l1;
    //ListNode* head = new ListNode(-1);
    //ListNode * temp = head;
    if(l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

代码3 网上看到了一种3行代码搞定的方案

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1 || (l2 && l1->val > l2->val)) 
            swap(l1, l2);
    if (l1) 
            l1->next = mergeTwoLists(l1->next, l2);
    return l1;
}

参考：http://www.cnblogs.com/grandyang/p/4086297.html