题目链接：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.

这道题的要求是将两个已经排好序的链表合并成1个有序链表。

这道题的思路比较简单，主要就是考察链表的处理。这里还是像Remove Nth Node From End of List一样先在链表前面加头，这样可以免去对链表头的特殊处理。接下来就是每次取两个链表前面较小的元素，直到有链表到达结尾。最后再将没有到达结尾的链表直接链接到合并的链表的后面，并返回合并后链表头后面的节点指针即可。

时间复杂度：O(n)

空间复杂度：O(1)

======

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        ListNode *h = new ListNode(0), *p = h;
        
        while(l1 != NULL && l2 != NULL)
        {
            if(l1 -> val < l2 -> val)
            {
                p -> next = l1;
                l1 = l1 -> next;
            }
            else
            {
                p -> next = l2;
                l2 = l2 -> next;
            }
            
            p = p -> next;
        }
        
        if(l1 != NULL)
            p -> next = l1;
        if(l2 != NULL)
            p -> next = l2;
        
        return h -> next;
    }
};