题解 | #合并两个排序的链表#

递归真是个好东西，我就是想保存一下，原帖链接

 * 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;
}