剑指Offer第16题：合并两个排序的链表

发表于 更新于 分类于

题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解题思路：创建一个新的链表头结点，比较两个链表的头结点值的大小，并将res->next指向值小的结点，直至有一个链表为空。之后合并剩下的非空链表即可。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode* Merge(ListNode* pHead1, ListNode* pHead2){
    ListNode* res = new ListNode(-1); //创建一个dummy head，防止两个链表中存在空链表
    ListNode* p = res;
    while (pHead1 && pHead2) {
        if (pHead1->val <= pHead2->val) { //比较两个链表头结点值的大小，将p指向值小的那个结点，之后该结点后移一位
            p->next = pHead1;
            pHead1 = pHead1->next;
        }
        else {
            p->next = pHead2;
            pHead2 = pHead2->next;
        }
        p = p->next; // p后移一位
    }
    if (pHead1) p->next = pHead1; // 合并其中一个空链表
    if (pHead2) p->next = pHead2;
    return res->next;
}