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

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(!pHead1){//特判
            return pHead2;
        }
        //一个链表插入到另一个链表中
        ListNode* res = new ListNode(INT_MIN);
        res->next = pHead1;
        ListNode* pre = res;
        ListNode* cur = pre->next; //用于pHead1
        while(pHead2){
            int hasInsert = 0;
            int isTail = 0;
            while(!hasInsert){
                if(cur->val > pHead2->val){
                    ListNode* tmp = pHead2->next;
                    pHead2->next = cur;
                    pre->next = pHead2;
                    pre = pre->next;
                    pHead2 = tmp;
                    hasInsert = 1;
                    break;
                }else if(cur->next){
                    pre = pre->next;
                    cur = pre->next;
                }else{
                    isTail = 1;
                    break;
                }
            }
            if(isTail == 1){
                cur->next = pHead2;
                break;
            }
        }
        return res->next;
        
    }
};