有序链表合并.md

两个有序链表的合并

问题描述

已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序

解决方案

1. 循环实现

**Tip:**类似归并排序。尤其注意两个链表都为空，和其中一个为空时的情况。只需要O（1）的空间。时间复杂度为O（max(len1, len2)）

算法代码如下：

Node * List_MergeSortedList_Loop(Node *head1, Node *head2) {
    if (head1 == nullptr) return head2;
    if (head2 == nullptr) return head1;

    Node *newHead = nullptr;
    if (head1->value < head2->value) {
        newHead = head1;
        head1 = head1->next;
    } else {
        newHead = head2;
        head2 = head2->next;
    }

    Node *tmp = newHead;
    while (head1 != nullptr && head2 != nullptr) {
        if (head1->value < head2->value) {
            tmp->next = head1;
            head1 = head1->next;
        } else {
            tmp->next = head2;
            head2 = head2->next;
        }
        tmp = tmp->next;
    }

    if (head1 == nullptr) tmp->next = head2;
    if (head2 == nullptr) tmp->next = head1;

    return newHead;
}

测试用例如下：

TEST(LinkedList, List_MergeSortedList_Loop) {
    Node nodeList1[10], nodeList2[10];

    List_Init(nodeList1, 5);
    EXPECT_TRUE(nullptr == List_MergeSortedList_Loop(nullptr, nullptr));
    EXPECT_TRUE("0 1 2 3 4 " == List_GetListString(List_MergeSortedList_Loop(nullptr, nodeList1)));
    EXPECT_TRUE("0 1 2 3 4 " == List_GetListString(List_MergeSortedList_Loop(nodeList1, nullptr)));

    List_Init(nodeList1, 5);
    List_Init(nodeList2, 5, 3);
    EXPECT_TRUE("0 1 2 3 3 4 4 5 6 7 " == List_GetListString(List_MergeSortedList_Loop(nodeList1, nodeList2)));

    List_Init(nodeList1, 5, 3);
    List_Init(nodeList2, 5);
    EXPECT_TRUE("0 1 2 3 3 4 4 5 6 7 " == List_GetListString(List_MergeSortedList_Loop(nodeList1, nodeList2)));
}

2. 递归实现

算法代码如下：

Node * List_MergeSortedList_Recursion(Node *head1, Node *head2) {
    if (head1 == nullptr) return head2;
    if (head2 == nullptr) return head1;

    Node *tmp = nullptr;
    if (head1->value < head2->value) {
        tmp = head1;
        tmp->next = List_MergeSortedList_Recursion(head1->next, head2);
    } else {
        tmp = head2;
        tmp->next = List_MergeSortedList_Recursion(head1, head2->next);
    }
    return tmp;
}

测试用例如下：

TEST(LinkedList, List_MergeSortedList_Recursion) {
    Node nodeList1[10], nodeList2[10];

    List_Init(nodeList1, 5);
    EXPECT_TRUE(nullptr == List_MergeSortedList_Recursion(nullptr, nullptr));
    EXPECT_TRUE("0 1 2 3 4 " == List_GetListString(List_MergeSortedList_Recursion(nullptr, nodeList1)));
    EXPECT_TRUE("0 1 2 3 4 " == List_GetListString(List_MergeSortedList_Recursion(nodeList1, nullptr)));

    List_Init(nodeList1, 5);
    List_Init(nodeList2, 5, 3);
    EXPECT_TRUE("0 1 2 3 3 4 4 5 6 7 " == List_GetListString(List_MergeSortedList_Recursion(nodeList1, nodeList2)));

    List_Init(nodeList1, 5, 3);
    List_Init(nodeList2, 5);
    EXPECT_TRUE("0 1 2 3 3 4 4 5 6 7 " == List_GetListString(List_MergeSortedList_Recursion(nodeList1, nodeList2)));
}