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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead1 ListNode类 
     * @param pHead2 ListNode类 
     * @return ListNode类
     */
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // write code here
	  //创建一个虚拟节点用于指向头节点
        ListNode* dummy=new ListNode(-1);
	  //创建一个cur节点把虚拟节点的值给它
        ListNode* cur=dummy;
	  //当pHead1为空时返回pHead2
        if(pHead1==nullptr){
            return pHead2;
        }
	  //当pHead2为空时返回pHead1
        if(pHead2==nullptr){
            return pHead1;
        }
	  //便利直到其中有一个链表为空
        while(pHead1!=nullptr&&pHead2!=nullptr){
		  //当pHead2->val>=pHead1->val时将cur指向头节点
      if(pHead2->val>=pHead1->val){
      cur->next=pHead1;
		//一旦进入if就让第一个链表的头节点向后走
      pHead1=pHead1->next;
      }
		  //当pHead1->val>=pHead2->val时将cur指向头节点
      else {
        cur->next=pHead2;
		//一旦进入if就让第二个链表的头节点向后走
        pHead2=pHead2->next;
      }
		 // 上面的if语句完成后cur向后走一位
    cur=cur->next;
        }
	  //因为上面只遍历完了一个链表所以要将漏下的链接到新链表后
        if(pHead1!=nullptr){
            cur->next=pHead1;
        }
        else if(pHead2!=nullptr){
            cur->next=pHead2;
        }
	  //创建一个节点让它被虚拟结点指向
    ListNode *p=dummy->next;
	  //释放虚拟节点
    delete dummy;
	  //返回新链表的头节点
    return p;
    }
    };