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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
#include <stdlib.h>
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    struct ListNode* p1 = pHead1;   //p1用于遍历第一个单链表
    struct ListNode* p2 = pHead2;   //p2用于遍历第二个单链表
    struct ListNode* s1=NULL;       //s1用于记录p1目前遍历到的结点，s1记录后p1往后移动
    struct ListNode* s2=NULL;       //s2用于记录p2目前遍历到的结点，s2记录后p1往后移动

    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode)); //新建立一个带头结点的单链表，方便操作
    newnode->next = NULL;
    struct ListNode* pnew = newnode;    //pnew辅助尾插，用于遍历记录新链表的最后一个几点，方便插入新结点

    while(p1&&p2){  //同时遍历两个单链表，只要有一个被遍历完就退出循环
        if(p1->val<=p2->val){   //如果此时p1的值小于p2的值，则将p1尾插到新链表尾部
            s1 = p1;    //s1记录此时p1遍历到的接地单
            p1 = p1->next;  //s1已经记录，p1向后走
            s1->next = NULL;    //尾插，所以s1->next =NULL
            pnew ->next = s1;   //将s1尾插进新链表 
            pnew = pnew->next;  //pnew向后遍历，记录此时新链表最后的一个结点
        }else{                  //如果此时p2的值小于p2的值，则将p2尾插到新链表尾部
            s2 = p2;
            p2 = p2->next;
            s2->next = NULL;
            pnew->next = s2;
            pnew = pnew->next;
        } 
    }

    if(p1==NULL){  //退出循环后，将没遍历完的那一个链表的剩余部分连接上新链表
        pnew->next = p2;
    }else{
        pnew->next = p1;
    }

    return newnode->next;   //返回一个不带头结点的单链表

}