刷题Q2 | 合并两个排序的链表

/**
 * 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
	    // 1、用头插法创建一个新链表（第3个链表），用于遍历存储较小节点，最后返回合并结果
        ListNode* vhead = new ListNode(-1);
        ListNode* cur = vhead;
	    // 2、在满足两个链表均不为空的情况下，开始比较链表元素大小，进行合并
        while(pHead1 && pHead2){
            if(pHead1->val <= pHead2->val){
                cur->next = pHead1; // 谁小，新链表就指向谁（存储较小节点）
                pHead1 = pHead1->next; // 存储好该链表的元素之后，向前推进，要存储后面的元素
            }
            else{
                cur->next = pHead2; // 和上面一样的道理，轮到链表2的元素小了，就存储它
                pHead2 = pHead2->next; // 存好链表2该元素，继续向前推进
            }
		    // 3、新链表通过cur指针存好了下一个元素，应该让cur指向末尾节点，一直充当尾指针，继续存储新元素
            cur = cur->next; 
        }
	  	// 跳出上面循环，意味着，至少有一个为空！如果链表1不空，那2肯定空，就接1。如果链表1空，那2空or不空，接2肯定对。
	    // 4、一旦有链表为空，那么就可以直接接上，当前的不为空的链表啦（如果都空，那接空指针也是无所谓啦）
        cur->next = pHead1 ? pHead1 : pHead2;
        return vhead->next; // 5、返回除去值为-1的头节点后，合并好的链表

    }
};

【参考图示】