LeetCode 中两个有序链表的合并题解

在 LeetCode 众多的算法题目中，两个有序链表的合并是一道经典且具有代表性的题目。它不仅考验我们对链表数据结构的理解，还能锻炼我们的编程思维和逻辑能力。

让我们来明确题目要求。给定两个升序排列的链表，我们需要将它们合并成一个新的升序链表，并返回合并后的头节点。

为了解决这个问题，我们可以采用一种比较直观的方法——双指针法。创建一个新的链表用于存储合并后的结果，并设置两个指针分别遍历两个输入链表。

在遍历过程中，比较两个指针所指向节点的值。较小的值将被添加到新链表中，并且对应的指针向前移动一步。当其中一个链表遍历完后，将另一个链表的剩余部分直接添加到新链表的末尾。

以下是使用 C++ 语言实现的代码示例：

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) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* curr = &dummy;

    while (l1 && l2) {
        if (l1->val < l2->val) {
            curr->next = l1;
            l1 = l1->next;
        } else {
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }

    curr->next = l1? l1 : l2;

    return dummy.next;
}

在这个代码中，我们首先创建了一个虚拟头节点 dummy，以便简化操作。然后通过循环比较两个链表节点的值，逐步构建合并后的链表。

对于这道题，关键在于对指针的操作和边界情况的处理。例如，当其中一个链表为空时，要正确地处理剩余部分的连接。

通过仔细分析题目要求，选择合适的数据结构和算法，我们能够高效地解决两个有序链表的合并问题。希望以上的题解能够帮助您更好地理解和掌握这一类型的题目。