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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pHead1 ListNode类
 * @param pHead2 ListNode类
 * @return ListNode类
 */
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    //int* nums = (int*)malloc(sizeof(int) * (m + n));
    struct ListNode* p1 = pHead1, *p2 = pHead2, *mid1,*mid2, *pe1, *pe2,*end;

    pe1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    pe2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    pe1->next = pHead1;
    pe2->next = pHead2;

    for (int i = 0; p1 != NULL && p2 != NULL; i++) {
        mid1 = p1->next;
        mid2=p2->next;
        if (p1->val <= p2->val&&p1->next!=NULL) { //p2的值更大          
            p1=p1->next;
            pe1=pe1->next;
        }else if(p1->val <= p2->val&&p1->next==NULL){
            p1->next=p2;
            break;
        } //else if(p1->val > p2->val&&p1->next==NULL) {
         else{
            pe2->next=mid2;
            pe1->next=p2;
            p2->next=p1;
            p2=mid2;
            pe1=pe1->next;
            if(p1==pHead1)
              pHead1=pe1;
        }
    }
    return pHead1;

}

注意事项：

1.如果P2中的节点插到了P1头结点前面，则需要修改PHead1

2.P1指向最后一个节点时，不能直接把P2节点剩余部分插入