题目描述

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.

题目大意

合并两个顺序排列的链表，并将新链表返回。新链表是把两个链表合并后的有序链表。

思路

输入问题：考虑为空！
新链表的第一个结点问题，由于一般情况下第一个结点都需要特殊处理，比较实用的解决办法是在第一个结点前增加一个虚拟的头结点(例如下面的head)，把实际的第一个结点一般化。最后输出的时候输出这个虚拟结点的下一个结点就OK。
如何为新链表选择下一个结点（已经虚拟出第一个结点了），这个比较容易，比大小就OK了，取小的并并在此链表前进一步。
注意循环的终止条件！
终止后并没有结束！

代码

// Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
    // l1、l2至少一个为空
    if(!l1 || !l2)
    {
        // (l1 && !l2)为true表示l2为空，则返回l1，否则返回l2
        // 返回l2的情况：（1）l1为空，l2不空；（2）l1、l2都为空。
        return l1 && !l2 ? l1 : l2;
    }

    ListNode *result = new ListNode(0);
    ListNode *head = result;
    while(l1 && l2)
    {
        if(l1->val <= l2->val)
        {
            head = head->next = l1;
            l1 = l1->next;
        }
        else
        {
            head = head->next = l2;
            l2 = l2->next;
        }
    }

    // l1或者l2不为空
    if(l1 || l2)
    {
        l1 ? (head->next=l1) : (head->next=l2);
    }
    return result->next;
}