LeetCode_21: Merge Two Sorted Lists

AI 摘要

文章介绍 LeetCode 合并两个有序链表问题，给定两个有序链表，要求合并为一个新的有序链表。示例输入 1->2->4、1->3->4，输出 1->1->2->3->4->4。题解采用归并思路，逐个比较节点值，将较小节点接入结果链表，遍历结束后接上剩余部分。时间复杂度 O(n)，空间复杂度 O(1)，并提供 C++ 和 Go 的 AC 代码。

AI 生成 · 仅供参考

# 引言

题目链接：https://leetcode.com/problems/merge-two-sorted-lists/description/

# 题目大意

合并两个有序链表并返回一个新的列表。

Example

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

# 题解

# 一句话题解

简单归并排序(由于这儿只有两条链表还是有序的, 所以时间复杂度退化为)

# 复杂度

时间复杂度 O(n)

空间复杂度 O(1)

# AC代码

c++版本

class Solution
{
  public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        ListNode *pRet = new ListNode(0);
        ListNode *curNode = pRet;
        while (nullptr != l1 && nullptr != l2)
        {
            if (l1->val < l2->val)
            {
                curNode->next = l1;
                l1 = l1->next;
            }
            else
            {
                curNode->next = l2;
                l2 = l2->next;
            }
            curNode = curNode->next;
        }
        if (nullptr != l1)
        {
            curNode->next = l1;
        }
        if (nullptr != l2)
        {
            curNode->next = l2;
        }
        return pRet->next;
    }
};

go版本

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	pRet := &ListNode{0, nil}
	curNode := pRet
	for nil != l1 && nil != l2 {
		if l1.Val < l2.Val {
			curNode.Next = l1
			l1 = l1.Next
		} else {
			curNode.Next = l2
			l2 = l2.Next
		}
		curNode = curNode.Next
	}
	if nil != l1 {
		curNode.Next = l1
	}
	if nil != l2 {
		curNode.Next = l2
	}
	return pRet.Next
}

文章关联

2 篇关联

顺着引用的连线，读见篇章交错的脉络

展开关系图

拖动平移 · Ctrl / ⌘ + 滚轮缩放 · 点击节点阅读使用 + / − 按钮缩放 · 放大视图后可拖动 · 点击节点阅读单指拖动平移 · 使用 + / − 按钮缩放 · 点击节点阅读

当前文章引用本文

引用列表

引用本文2

LeetCode_23: Merge k Sorted Lists
AI 摘要
文章是 LeetCode“合并 K 个排序链表”的题解。题目要求将 k 个已排序链表合并为一个排序列表。题解核心是复用第 21 题“合并两个有序链表”的方法，再借用归并排序的分治思想，对链表两两合并，逐步缩小规模，直到只剩一个链表。时间复杂度为 O(nlogn)，空间复杂度为 O(1)。最后给出 C++ 与 Go 的 AC 代码实现。
LeetCode Programming
AI 摘要
本文是作者为缓解拖延、练习 Go 语言而开启的 LeetCode 刷题记录，兼作个人题解。文中先介绍 C++ 输入输出加速技巧，通过 ios::sync_with_stdio(false) 解除 C/C++ 流同步、cin.tie(nullptr) 解除 cin 与 cout 绑定来提升效率；随后汇总多道 LeetCode 题解，列出题号、题目、难度及链接，涵盖第1至32题等。

本文引用0

暂无

LeetCode_4: Median of Two Sorted Arrays
AI 摘要
本文讲解 LeetCode“两个有序数组的中位数”解法。题目要求合并两个升序数组并求中位数，官方期望复杂度为 O(log(m+n))。文章先说明中位数取值规则，再给出两种方法：归并扫描法，复杂度 O(m+n)；以及转化为寻找第 k 小数，通过比较两数组第 k/2 个元素并每次剔除一半，递归求得第 k 小，复杂度 O(log(m+n))，并附 C++ 与 Go 实现。
LeetCode_2: Add Two Numbers
AI 摘要
文章是 LeetCode“两数相加”的题解。题目用两个倒序链表表示非负整数，每位为一个节点，要求相加后返回倒序链表。题解指出倒序链表正好从低位到高位存储，因此可同时遍历两链表，逐位相加并维护进位。空节点值按 0 处理，新节点存当前和的个位，进位为和除以 10；遍历结束后若仍有进位则追加节点。时间复杂度 O(n)。代码给出 C++ 和 Go 两种实现。
LeetCode_26: Remove Duplicates from Sorted Array
AI 摘要
本文介绍 LeetCode“删除排序数组中的重复项”题解。题目要求对已排序数组原地去重，仅用 O(1) 额外空间修改输入，返回新长度，超出部分无需处理。核心思路是顺序遍历，用 index 指向下一个待放位置，当当前元素与前一个不同时，将其写入 index 并递增，同时计数。时间复杂度 O(n)，空间复杂度 O(1)，并给出 C++ 与 Go 实现。
LeetCode_1: Two Sum
AI 摘要
本文介绍 LeetCode 两数之和题解。题目要求给定整数序列和目标值，找出两个不同元素使它们之和等于目标值，并假设仅有唯一解。核心思路是遍历数组，用哈希表记录已访问数值及其下标；每遇到当前值，先查询目标值与当前值之差是否已在表中，若存在则返回两下标，否则把当前值存入表中。该方法时间复杂度为 O(n)，文中给出 C++ 和 Go 实现代码。

本文作者：Seiun@繁夜
本文链接：https://onlyzyx.com/posts/12203.html
版权声明：本站所有文章除特别声明外，均采用 (CC)BY-NC-SA 许可协议。转载请注明出处！

循着字句，邂逅星光

输入关键词

发现内容

快速直达

LeetCode_21: Merge Two Sorted Lists

# 引言

# 题目大意

# 题解

# 一句话题解

# 复杂度

# AC代码

文章关联

引用本文2

本文引用0

文章关联

标签漫游

再读一篇

最近的声音

# 引言

# 题目大意

# 题解

# 一句话题解

# 复杂度

# AC代码

文章关联

引用本文2

本文引用0

继续阅读

LeetCode_20: Valid Parentheses

LeetCode_22: Generate Parentheses