code4offer-12

合并两个排序的链表

题目描述

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

分析

非递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
    if (!pHead1) return pHead2;
    if (!pHead2) return pHead1;

    ListNode* head = NULL;
    if (pHead1->val <= pHead2->val) {
        head = pHead1;
        pHead1 = pHead1->next;
    } else {
        head = pHead2;
        pHead2 = pHead2->next;
    }

    ListNode* tmpHead = head;

    while (pHead1 && pHead2) {
        if (pHead1->val <= pHead2->val) {
            tmpHead->next = pHead1;
            pHead1 = pHead1->next;
        } else {
            tmpHead->next = pHead2;
            pHead2 = pHead2->next;
        }

        tmpHead = tmpHead->next;
    }

    // 剩下的直接接到后面
    if (pHead1) tmpHead->next = pHead1;
    if (pHead2) tmpHead->next = pHead2;

    return head;
}

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
    if (!pHead1) return pHead2;
    if (!pHead2) return pHead1;

    ListNode* head = NULL;
    if (pHead1->val <= pHead2->val) {
        head = pHead1;
        pHead1 = pHead1->next;
    } else {
        head = pHead2;
        pHead2 = pHead2->next;
    }

    head->next = Merge(pHead1, pHead2);

    return head;
}