合并两个排序的链表

题目：

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例:

输入：{1,3,5},{2,4,6}

返回值：{1,2,3,4,5,6}

输入：{},{}

返回值：{}

输入：{-1,2,4},{1,3,4}

返回值：{-1,1,2,3,4,4}

解题思路：

采用递归法对两个链表的节点进行比较，将小的头节点取出，并将其添加到新的链表后面，剩下的部分再进行比较，重复上述过程，直到两个链表为空。

代码示例：

```/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    if(pHead1 == NULL)
        return pHead2;
    if(pHead2 == NULL)
        return pHead1;
    struct ListNode *phead = NULL;
    if(pHead1->val < pHead2->val){
        phead = pHead1;
        phead->next = Merge(pHead1->next, pHead2);
    }else{
        phead = pHead2;
        phead->next = Merge(pHead1, pHead2->next);
    }
    return phead;
}