leetcode：21. 合并两个有序链表

题目链接

        21. 合并两个有序链表 - 力扣（LeetCode）

题目描述

为什么可以用递归

1. 递归 = 人脑 + 计算机递归结构
2. 递归是人脑借助计算机递归结构去解决问题
3. 人脑发现问题具有递归结构，于是借助计算机递归结构去解决问题
4. 所以递归算法脱离计算机之后根本不存在
5. 我们采用递归算法把问题解出来，仅仅只是借助了计算机的递归结构，完全是计算机的功劳
6. 对于递归来说，计算机为我们承担了暴力计算的全部。人脑在此时的价值仅仅体现在把问题交给计算机而已
7. 对于递归算法来说人脑的价值不体现在：帮助计算机更轻松的计算，减轻计算机负担；也不体现在：脱离计算机，在完全靠人脑的情况下，通过更聪明的方式让人脑解决问题。
8. 也就是说递归算法几乎配不上算法这两个字，所谓递归算法的全部内容仅仅只是：发现这个问题具有递归结构，正好借用计算机递归计算，交给计算机去计算。仅此而已

解法1：递归法

class Solution {
public:
    ListNode* dfs(ListNode* list1, ListNode* list2)
    {
        if (list1 == nullptr)    return list2;
        if (list2 == nullptr)    return list1;

        if (list1->val <= list2->val)
        {
            list1->next = dfs(list1->next, list2);
            return list1;
        }

        list2->next = dfs(list2->next, list1);
        return list2;
    }

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* object_head = dfs(list1, list2);
        return object_head;
    }
};

递归分析

        大家可以先阅读一下：leetcode:面试题 08.06. 汉诺塔问题-CSDN博客
        本问题与汉诺塔问题有何不同呢？

1. 汉诺塔问题的递归主逻辑中可是没有if语句做条件判断的
2. 本问题根据条件判断语句，依照实际情况有选择的去做递归
3. 汉诺塔问题中不需要分情况去有选择的递归
4. 如果本问题不是采用有选择的递归，将会非常复杂。

解法2：利用容器multimap

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr && list2 == nullptr) {
            return nullptr;
        }

        multimap<int, ListNode*> myMultimap;
        while (list1)
        {
            myMultimap.insert(make_pair(list1->val, list1));
            list1 = list1->next;
        }
        while (list2)
        {
            myMultimap.insert(make_pair(list2->val, list2));
            list2 = list2->next;
        }
        ListNode* tmp;
        auto it = myMultimap.begin();
        if (it != myMultimap.end()) {
            tmp = it->second;
        }

        int count = 1;
        for (const auto& pair : myMultimap)
        {
            if (count > 1)
            {
                tmp->next = pair.second;
                tmp = pair.second;
            }
            count++;
        }
        tmp->next = nullptr;
        return myMultimap.begin()->second;
    }
};

解法2分析

1. 该题是为了排序，且有重复元素，正好利用multimap的特性
2. 时间复杂度是O(nlogn)，递归法时间复杂度是O(n)