【LeetCode热题100】21. 合并两个有序链表（链表）

一.题目要求

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

二.题目难度

简单

三.输入样例

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：
输入：l1 = [], l2 = []
输出：[]

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

提示：
两个链表的节点数目范围是 [0, 50]
-100 l1 和 l2 均按 非递减顺序 排列

四.解题思路

新建一个头节点，而后遍历尾插，最后插入较长的未处理链。

五.代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 服务器托管网*     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1) return list2;
        if(!list2) return list1;
        //ListNode* ans = list1->val val ? list1 : list2;
        ListNode head(0, nullptr);
        ListNode* p = list1 ,*q = list2 ,*list12 = &head ,*w= list12;
        while(p && q)
        {
            if(p->val  q->val)
            {
                w->next = p;
                p = p->next;
                w = w->next;
            }
            else
            {
                w->next = q;
                q = q->next;
                w = w->next;          
            }
        }
        if(p)
        {
                w->next = p;
        }
        else
        {
                w->next = q;
        }    

        return list12->next;
    }
};

六.题目总结

递归

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int va服务器托管网l;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        //给我什么 我要干什么 我给什么 递归退出值 
        //给我两个待处理的结点，
        //我要判断插入哪个
        //我返回我要插入的那个节点
        //一个空了就只能插入另一个了
        if(!list1) return list2;
        if(!list2) return list1;

        if(list1->val  list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else 
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;           
        }
    }
};

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 【监督学习之决策树和随机森林】

曾梦想执剑走天涯，我是程序猿【AK】 目录 简述概要 知识图谱 决策树（Decision Tree） 随机森林（Random Forest） 简述概要 了解决策树和随机森林 知识图谱 决策树和随机森林都是机器学习中常用的算法，它们在处理分类和回归问题时表现出色…