【剑指Offer】（链表）合并两个排序的链表

深藏阁楼爱情的钟 2022-03-17 14:22 140阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_d8b6b4358f774294a89de2a6ac4d9337_tpId_13_tqId_11169_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

#### 解决方法 ####

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/
    class Solution { 
    public:
        ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
        { 
            //特殊情况
            if (!pHead1) return pHead2;
            if (!pHead2) return pHead1;
            //初始化首节点
            ListNode *head=nullptr;
            if (pHead1->val<pHead2->val) { head=pHead1; pHead1=pHead1->next;} 
            else { head=pHead2; pHead2=pHead2->next;}
            ListNode *rhead=head;
            //合并链表
            while(pHead1 && pHead2){ 
                if (pHead1->val<pHead2->val) { head->next=pHead1; pHead1=pHead1->next;}
                else { head->next=pHead2; pHead2=pHead2->next;}
                head=head->next;
            }
            if (!pHead1) head->next=pHead2;
            else head->next=pHead1;
            return rhead;
        }
    };

[https_www.nowcoder.com_practice_d8b6b4358f774294a89de2a6ac4d9337_tpId_13_tqId_11169_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking