c++-c++编程基础之leetcode题解第21题合并两个有序链表.zip资源-CSDN文库

共1个文件

md：1个

需积分: 1 146 浏览量 2024-04-07 05:22:03 上传评论收藏 2KB ZIP 举报

在C++编程中，LeetCode是一个非常受欢迎的在线平台，用于练习和提升编程技能，特别是算法和数据结构。第21题"合并两个有序链表"是其中一道经典的题目，它涉及到链表的操作，这对于理解和掌握C++中的链表非常重要。下面我们将详细探讨这个问题以及如何用C++解决它。我们需要理解链表的概念。链表是一种线性数据结构，与数组不同，链表的元素并不在内存中连续存储。每个元素（节点）包含两部分：数据和指向下一个元素的指针。在C++中，我们可以定义一个结构体或类来表示链表节点。 ```cpp struct ListNode { int val; // 节点值 ListNode *next; // 指向下一个节点的指针 ListNode(int x) : val(x), next(NULL) {} // 构造函数 }; ``` 题目21要求我们将两个已排序的链表合并为一个有序链表。这可以通过迭代或递归的方式来实现。这里我们展示一个迭代的解决方案： ```cpp ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); // 创建虚拟头节点，方便操作 ListNode* tail = &dummy; // 初始化尾指针 while (l1 && l2) { // 当两个链表都不为空时 if (l1->val < l2->val) { // 如果l1的值更小，将l1接在尾部 tail->next = l1; l1 = l1->next; } else { // 否则将l2接在尾部 tail->next = l2; l2 = l2->next; } tail = tail->next; // 更新尾指针 } // 将剩余的链表接在尾部 tail->next = l1 ? l1 : l2; return dummy.next; // 返回新链表的头节点 } ``` 在这个解决方案中，我们首先创建一个虚拟头节点`dummy`，然后通过`tail`指针跟踪合并后链表的新尾部。我们比较`l1`和`l2`的当前节点值，将较小值的节点接在`tail`后面，并更新`l1`或`l2`到下一个节点。当其中一个链表遍历完后，将另一个链表剩余的部分接到`tail`后面。最后返回`dummy.next`作为合并后链表的头节点。这个题目不仅锻炼了对链表的基本操作，如遍历和节点插入，还要求程序员能够处理边界条件，如当一个链表为空时。通过解决这样的问题，你可以深化对C++中动态数据结构的理解，并提高算法设计能力。在LeetCode上进行此类练习，有助于准备面试和提高实际编程项目中的问题解决能力。

资源推荐

资源详情

资源评论

收起资源包目录

c++_c++编程基础之leetcode题解第21题合并两个有序链表.zip （1个子文件）

c++_c++编程基础之leetcode题解第21题合并两个有序链表

README.md 4KB

# [21. Merge Two Sorted Lists (Easy)](https://leetcode.com/problems/merge-two-sorted-lists/) Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.   Example 1: <img alt="" src="https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg" style="width: 662px; height: 302px;"> <pre>Input: l1 = [1,2,4], l2 = [1,3,4] Output: [1,1,2,3,4,4] </pre> Example 2: <pre>Input: l1 = [], l2 = [] Output: [] </pre> Example 3: <pre>Input: l1 = [], l2 = [0] Output: [0] </pre>   Constraints: <ul> <li>The number of nodes in both lists is in the range <code>[0, 50]</code>.</li> <li><code>-100 <= Node.val <= 100</code></li> <li>Both <code>l1</code> and <code>l2</code> are sorted in non-decreasing order.</li> </ul> **Related Topics**: [Linked List](https://leetcode.com/tag/linked-list/), [Recursion](https://leetcode.com/tag/recursion/) **Companies**: [Amazon](https://leetcode.com/company/amazon), [Microsoft](https://leetcode.com/company/microsoft), [Facebook](https://leetcode.com/company/facebook), [Google](https://leetcode.com/company/google), [Adobe](https://leetcode.com/company/adobe), [Apple](https://leetcode.com/company/apple), [Bloomberg](https://leetcode.com/company/bloomberg), [Yahoo](https://leetcode.com/company/yahoo), [Arista Networks](https://leetcode.com/company/arista-networks), [Uber](https://leetcode.com/company/uber), [Indeed](https://leetcode.com/company/indeed), [Cisco](https://leetcode.com/company/cisco), [Tencent](https://leetcode.com/company/tencent), [Airbnb](https://leetcode.com/company/airbnb), [Oracle](https://leetcode.com/company/oracle), [IBM](https://leetcode.com/company/ibm), [Huawei](https://leetcode.com/company/huawei), [Paypal](https://leetcode.com/company/paypal), [Yandex](https://leetcode.com/company/yandex) **Similar Questions**: * [Merge k Sorted Lists (Hard)](https://leetcode.com/problems/merge-k-sorted-lists/) * [Merge Sorted Array (Easy)](https://leetcode.com/problems/merge-sorted-array/) * [Sort List (Medium)](https://leetcode.com/problems/sort-list/) * [Shortest Word Distance II (Medium)](https://leetcode.com/problems/shortest-word-distance-ii/) * [Add Two Polynomials Represented as Linked Lists (Medium)](https://leetcode.com/problems/add-two-polynomials-represented-as-linked-lists/) ## Solution 1. ```cpp // OJ: https://leetcode.com/problems/merge-two-sorted-lists/ // Author: github.com/lzl124631x // Time: O(A + B) // Space: O(1) class Solution { public: ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode head, *tail = &head; while (a && b) { if (a->val <= b->val) { tail->next = a; a = a->next; } else { tail->next = b; b = b->next; } tail = tail->next; } tail->next = a ? a : b; return head.next; } }; ``` ## Solution 2. ```cpp // OJ: https://leetcode.com/problems/merge-two-sorted-lists/ // Author: github.com/lzl124631x // Time: O(A + B) // Space: O(1) class Solution { public: ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode head, *p = &head; head.next = a; while (p->next && b) { if (p->next->val > b->val) { auto node = b; b = b->next; node->next = p->next; p->next = node; } p = p->next; } if (b) p->next = b; return head.next; } }; ```

评论收藏

内容反馈