【力扣刷题实战】合并两个有序链表

大家好，我是小卡皮巴拉

文章目录

力扣题目：合并两个有序链表

题目描述

示例 1：

示例 2：

示例 3：

解题思路

问题理解

算法选择

具体思路

解题要点

完整代码（C语言）

兄弟们共勉！！！

每篇前言

博客主页：小卡皮巴拉

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。

力扣题目：合并两个有序链表

原题链接：合并两个有序链表

题目描述

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

示例 1：

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

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

解题思路

问题理解

给定两个升序排列的单链表list1和list2，要求合并为一个新的升序链表并返回。

算法选择

使用双指针遍历法，通过比较两个链表的当前节点值，依次选择较小的节点构建新的链表。

具体思路

初始检查：

首先，检查list1和list2是否为空。如果其中一个为空，直接返回另一个链表，因为空链表与任何链表合并的结果就是非空的那个链表本身。

初始化指针：

使用l1和l2分别指向list1和list2的头节点。

创建一个哨兵节点（占位节点）newHead，并同时让它作为新链表的尾节点newTail。这里哨兵节点的作用是简化链表为空时的处理，但会引入额外的内存分配和释放。

合并过程：

使用一个while循环，只要l1和l2都不为空，就继续执行循环。

在循环内部，比较l1和l2当前节点的值：

如果l1->val小于l2->val，则将l1当前节点接到newTail后面，并更新newTail和l1指针。

否则，将l2当前节点接到newTail后面，并更新newTail和l2指针。

处理剩余节点：

当while循环结束时，l1或l2中至少有一个为空。此时，将非空的链表直接接到newTail后面。

返回结果：

由于我们使用了哨兵节点，所以合并后的链表头节点是newHead->next。

释放哨兵节点newHead占用的内存，并返回合并后的链表头节点。

解题要点

边界处理：若任一链表为空，直接返回非空链表。
双指针遍历：使用双指针分别遍历两个链表，比较节点值。
选择接入：将较小值的节点接入新链表，并更新指针。
结果返回：返回新链表头（注意哨兵节点的处理与内存释放）。

完整代码（C语言）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{// 对空链表进行处理if (list1 == NULL) {return list2;}if (list2 == NULL) {return list1;}ListNode* l1 = list1;ListNode* l2 = list2;// 创建新链表的头结点和尾结点ListNode *newHead, *newTail;//由于空链表情况特殊，需特殊处理，我们采用申请哨兵位（占位结点）的方式来简化代码//这样后续的代码无需再判断链表是否为空// 创建非空链表newHead = newTail = (ListNode*)malloc(sizeof(ListNode));while (l1 && l2) {if (l1->val < l2->val) {// l1插入新链表中newTail->next = l1;newTail = newTail->next;l1 = l1->next;} else {// l2插入新链表中newTail->next = l2;newTail = newTail->next;l2 = l2->next;}}// 跳出循环，只有两种情况：1. l1走到空 2. l2走到空if (l1) {newTail->next = l1;}if (l2) {newTail->next = l2;}//将哨兵位(占位结点)归还给操作系统ListNode* retHead = newHead->next;free(newHead);newHead = NULL;return retHead;
}