【一刷《剑指Offer》】面试题 17:合并两个排序的链表

简介: 【一刷《剑指Offer》】面试题 17:合并两个排序的链表

力扣对应题目链接:21. 合并两个有序链表 - 力扣(LeetCode)

核心考点:链表合并。


一、《剑指Offer》内容


二、分析题目

这道题的解题方法:

  1. 可以选择一个一个节点的归并。
  2. 可以采用递归来完成。

三、代码

1、易于理解的写法(归并)

/**
 * 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==nullptr) return list2;
        if(list2==nullptr) return list1;
 
        //合并无非是比较各自首节点谁小,就把该节点从原链表中删除,再尾插到新节点处,比较时两个链表任何一个都不能为空
        ListNode* newHead=nullptr;
        ListNode* end=nullptr;
        while(list1 && list2)
        {
            ListNode* cur=nullptr;
 
            //先判定拿那个节点
            if(list1->val<list2->val) cur=list1;
            else cur=list2;
 
            //再在指定链表中,删除目标节点
            if(cur==list1) list1=list1->next;
            else list2=list2->next;
 
            //尾插到新链表,这里要考虑第一次插入的情况
            if(newHead==nullptr)
            {
                newHead=cur;
                end=cur;
            }
            else
            {
                end->next=cur;
                end=end->next;
            }
        }
 
        //合并后可能会有几种情况:1.pHead1为空 2.pHead2为空 3.都为空(合并完成)
        if(list1) end->next=list1;
        if(list2) end->next=list2;
        return newHead;
    }
};

2、递归

//写法一
/**
 * 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==nullptr) return list2;
        if(list2==nullptr) return list1;
        if(list1->val<=list2->val)
        {
            list1->next=mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next=mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};
 
//写法二
/**
 * 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==nullptr) return list2;
        if(list2==nullptr) return list1;
        ListNode* newHead=nullptr;
        if(list1->val<=list2->val)
        {
            newHead=list1;
            list1=list1->next;
        }
        else
        {
            newHead=list2;
            list2=list2->next;
        }
        newHead->next=mergeTwoLists(list1, list2);
        return newHead;
    }
};


相关文章
|
1月前
|
存储 人工智能 测试技术
每日练习之排序——链表的合并;完全背包—— 兑换零钱
每日练习之排序——链表的合并;完全背包—— 兑换零钱
18 2
|
2月前
23. 合并 K 个升序链表
23. 合并 K 个升序链表
35 3
|
1月前
23.合并K个升序链表
23.合并K个升序链表
|
1月前
|
存储 SQL 算法
LeetCode 83题:删除排序链表中的重复元素【面试】
LeetCode 83题:删除排序链表中的重复元素【面试】
|
1月前
|
存储 算法 数据挖掘
Leetcode二十三题:合并K个升序链表【22/1000 python】
Leetcode二十三题:合并K个升序链表【22/1000 python】
|
2月前
|
索引
【力扣刷题】回文链表、环形链表、合并两个有序链表
【力扣刷题】回文链表、环形链表、合并两个有序链表
23 0
|
2月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
2月前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
2月前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
|
2月前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵