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

/**
 * 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
        // nullptr 
        if (pHead1 == nullptr && pHead2 == nullptr) {
            return nullptr;
        }
        if (pHead1 == nullptr) {
            return pHead2;
        } 
        if (pHead2 == nullptr) {
            return pHead1;
        }

        ListNode* curr1 = pHead1;
        ListNode* curr2 = pHead2;
        ListNode* jointHead = new ListNode(0);
        ListNode* curr = jointHead;

        // if (pHead1->val > pHead2->val){
        //     jointHead = pHead1;
        //     prev = jointHead;
        // } else {
        //     jointHead = pHead2;
        //     prev = jointHead;
        // }

        while (curr1 != nullptr || curr2 != nullptr) {
            if (curr1 == nullptr) {
                curr->next = curr2;
                break;
            } else if (curr2 == nullptr) {
                curr->next = curr1;
                break;
            } 
            
            if (curr1->val <= curr2->val) {
                    curr->next = curr1;
                    curr1 = curr1->next;
                } else {
                    curr->next = curr2;
                    curr2 = curr2->next;
                }
                curr = curr->next;
            
        }

        return jointHead->next;
        //一个已经为空了，直接返回另一个
        // if(pHead1 == NULL)
        //     return pHead2;
        // if(pHead2 == NULL)
        //     return pHead1;
        // //加一个表头
        // ListNode* head = new ListNode(0);
        // ListNode* cur = head;
        // //两个链表都要不为空
        // while(pHead1 && pHead2){
        //     //取较小值的节点
        //     if(pHead1->val <= pHead2->val){
        //         cur->next = pHead1;
        //         //只移动取值的指针
        //         pHead1 = pHead1->next;
        //     }else{
        //         cur->next = pHead2;
        //         //只移动取值的指针
        //         pHead2 = pHead2->next;
        //     }
        //     //指针后移
        //     cur = cur->next;
        // }
        // //哪个链表还有剩，直接连在后面
        // if(pHead1)
        //     cur->next = pHead1;
        // else
        //     cur->next = pHead2;
        // //返回值去掉表头
        // return head->next;
    }
};

注意：需要单独的维护一个指针是用作输出的链表的索引指针，并且需要有另外两个指针去维护待链接的子链表的相关索引#剑指offer#