admin管理员组文章数量:1033650
【初探数据结构】链表OJ算法——哨兵位（合并两个有序链表详解）
哨兵位（Sentinel Node）的作用
哨兵位是链表中的一个特殊节点，它并不保存有效数据，只是作为标识存在。使用哨兵位有以下几个好处：
- 统一处理：哨兵位使得链表的插入和删除操作可以统一处理，无需区分链表为空、头节点或尾节点等特殊情况。
- 简化代码：避免了空链表的处理、头节点的特殊处理等复杂情况，使得代码更加简洁。
下面我们来实战演练。
实战演练
合并两个有序链表 - 力扣（LeetCode）
这道题的解法很多，这里我们使用最优的方法——双指针遍历
思路讲解
通过两个指针同时遍历两个链表，逐个比较链表中的节点，将较小的节点接到合并后的链表上，直到一个链表遍历完成，再将另一个链表中剩余的部分直接接到结果链表后。
详细步骤
1. 处理特殊情况（边界条件）
代码语言：javascript代码运行次数：0运行复制if(list1 == NULL)
return list2;
if(list2 == NULL)
return list1;如果其中一个链表为空，直接返回另一个链表。这样可以避免后续操作中对空链表的额外处理。
2. 创建哨兵节点
代码语言：javascript代码运行次数：0运行复制struct ListNode* tail = NULL, *guard = NULL;
guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
tail->next = NULL;- 创建一个哨兵节点
guard，该节点不会保存实际的数据。它的作用是简化链表的操作，特别是头节点的处理。因为如果直接操作链表头节点，可能需要单独判断头节点是否为空或其他边界情况，使用哨兵节点后，我们就可以统一处理所有节点的插入。 tail指针用于指向合并链表的尾部。通过这个指针，我们可以方便地将新的节点插入到合并后的链表中。
3. 初始化两个指针，遍历两个链表
代码语言：javascript代码运行次数：0运行复制struct ListNode* cur1 = list1;
struct ListNode* cur2 = list2;cur1和cur2分别指向两个输入链表list1和list2的头节点。我们将使用这两个指针遍历两个链表，进行比较并合并。
4. 合并两个链表
代码语言：javascript代码运行次数：0运行复制while(cur1 && cur2) {
if(cur1->val < cur2->val) {
tail->next = cur1;
cur1 = cur1->next;
tail = tail->next;
} else {
tail->next = cur2;
cur2 = cur2->next;
tail = tail->next;
}
}- 这里使用一个
while循环，循环条件是cur1和cur2都不为空。也就是说，只有当两个链表中都有节点时，才会进入循环。 - 在循环内部，比较
cur1和cur2所指向节点的值，选择较小的节点加入到合并后的链表中：- 如果
cur1的值小于cur2的值，就将cur1节点连接到tail的next上，并将cur1向后移动一个节点。 - 否则，将
cur2节点连接到tail的next上，并将cur2向后移动一个节点。
- 如果
- 每次将新的节点连接到
tail之后，更新tail指针，指向合并链表的最后一个节点。
5. 处理剩余节点
代码语言：javascript代码运行次数：0运行复制if(cur1)
tail->next = cur1;
if(cur2)
tail->next = cur2;- 在上面的
while循环结束后，可能会有一个链表的节点已经全部被处理完，另一个链表中还有节点没有被合并。 - 如果
cur1指向的链表中还有节点未处理（即cur1不为空），将剩余的cur1节点直接接到合并链表的尾部。 - 同理，如果
cur2指向的链表中还有节点未处理（即cur2不为空），将剩余的cur2节点直接接到合并链表的尾部。
6. 返回合并后的链表
代码语言：javascript代码运行次数：0运行复制struct ListNode* head = guard->next;
free(guard);
return head;- 合并后的链表的头节点是
guard->next，因为guard本身是一个哨兵节点，不保存实际的数据。返回guard->next就是合并后的链表的头节点。 - 最后，释放掉
guard节点占用的内存，因为guard节点已经不再需要。
完整代码
代码语言：javascript代码运行次数：0运行复制struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
// 如果list1为空，返回list2
if(list1 == NULL)
return list2;
// 如果list2为空，返回list1
if(list2 == NULL)
return list1;
struct ListNode* tail = NULL, *guard = NULL;
struct ListNode* cur1 = list1;
struct ListNode* cur2 = list2;
// 创建一个哨兵节点guard，方便操作链表头
guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
tail->next = NULL;
// 合并两个链表
while(cur1 && cur2) {
// 判断当前cur1的值与cur2的值，选择较小的节点
if(cur1->val < cur2->val) {
tail->next = cur1;
cur1 = cur1->next; // 移动cur1指针
tail = tail->next; // 更新tail指针
} else {
tail->next = cur2;
cur2 = cur2->next; // 移动cur2指针
tail = tail->next; // 更新tail指针
}
}
// 如果cur1还有剩余，连接到tail
if(cur1)
tail->next = cur1;
// 如果cur2还有剩余，连接到tail
if(cur2)
tail->next = cur2;
// 头指针是guard的下一个节点
struct ListNode* head = guard->next;
// 释放哨兵节点
free(guard);
return head;
}结语
如果这道题不用哨兵位，你将会被一个错误搞的焦头烂额——对空指针解引用，不相信的话你可以去试试，你一定会影响深刻的。
通过这道题，是不是觉得哨兵位真的很香？非常省事，特别是这种多链表的联合问题，我们一定要留个心眼。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-21，如有侵权请联系 cloudcommunity@tencent 删除遍历链表算法指针数据结构【初探数据结构】链表OJ算法——哨兵位（合并两个有序链表详解）
哨兵位（Sentinel Node）的作用
哨兵位是链表中的一个特殊节点，它并不保存有效数据，只是作为标识存在。使用哨兵位有以下几个好处：
- 统一处理：哨兵位使得链表的插入和删除操作可以统一处理，无需区分链表为空、头节点或尾节点等特殊情况。
- 简化代码：避免了空链表的处理、头节点的特殊处理等复杂情况，使得代码更加简洁。
下面我们来实战演练。
实战演练
合并两个有序链表 - 力扣（LeetCode）
这道题的解法很多，这里我们使用最优的方法——双指针遍历
思路讲解
通过两个指针同时遍历两个链表，逐个比较链表中的节点，将较小的节点接到合并后的链表上，直到一个链表遍历完成，再将另一个链表中剩余的部分直接接到结果链表后。
详细步骤
1. 处理特殊情况（边界条件）
代码语言：javascript代码运行次数：0运行复制if(list1 == NULL)
return list2;
if(list2 == NULL)
return list1;如果其中一个链表为空，直接返回另一个链表。这样可以避免后续操作中对空链表的额外处理。
2. 创建哨兵节点
代码语言：javascript代码运行次数：0运行复制struct ListNode* tail = NULL, *guard = NULL;
guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
tail->next = NULL;- 创建一个哨兵节点
guard，该节点不会保存实际的数据。它的作用是简化链表的操作，特别是头节点的处理。因为如果直接操作链表头节点，可能需要单独判断头节点是否为空或其他边界情况，使用哨兵节点后，我们就可以统一处理所有节点的插入。 tail指针用于指向合并链表的尾部。通过这个指针，我们可以方便地将新的节点插入到合并后的链表中。
3. 初始化两个指针，遍历两个链表
代码语言：javascript代码运行次数：0运行复制struct ListNode* cur1 = list1;
struct ListNode* cur2 = list2;cur1和cur2分别指向两个输入链表list1和list2的头节点。我们将使用这两个指针遍历两个链表，进行比较并合并。
4. 合并两个链表
代码语言：javascript代码运行次数：0运行复制while(cur1 && cur2) {
if(cur1->val < cur2->val) {
tail->next = cur1;
cur1 = cur1->next;
tail = tail->next;
} else {
tail->next = cur2;
cur2 = cur2->next;
tail = tail->next;
}
}- 这里使用一个
while循环，循环条件是cur1和cur2都不为空。也就是说，只有当两个链表中都有节点时，才会进入循环。 - 在循环内部，比较
cur1和cur2所指向节点的值，选择较小的节点加入到合并后的链表中：- 如果
cur1的值小于cur2的值，就将cur1节点连接到tail的next上，并将cur1向后移动一个节点。 - 否则，将
cur2节点连接到tail的next上，并将cur2向后移动一个节点。
- 如果
- 每次将新的节点连接到
tail之后，更新tail指针，指向合并链表的最后一个节点。
5. 处理剩余节点
代码语言：javascript代码运行次数：0运行复制if(cur1)
tail->next = cur1;
if(cur2)
tail->next = cur2;- 在上面的
while循环结束后，可能会有一个链表的节点已经全部被处理完，另一个链表中还有节点没有被合并。 - 如果
cur1指向的链表中还有节点未处理（即cur1不为空），将剩余的cur1节点直接接到合并链表的尾部。 - 同理，如果
cur2指向的链表中还有节点未处理（即cur2不为空），将剩余的cur2节点直接接到合并链表的尾部。
6. 返回合并后的链表
代码语言：javascript代码运行次数：0运行复制struct ListNode* head = guard->next;
free(guard);
return head;- 合并后的链表的头节点是
guard->next，因为guard本身是一个哨兵节点，不保存实际的数据。返回guard->next就是合并后的链表的头节点。 - 最后，释放掉
guard节点占用的内存，因为guard节点已经不再需要。
完整代码
代码语言：javascript代码运行次数：0运行复制struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
// 如果list1为空，返回list2
if(list1 == NULL)
return list2;
// 如果list2为空，返回list1
if(list2 == NULL)
return list1;
struct ListNode* tail = NULL, *guard = NULL;
struct ListNode* cur1 = list1;
struct ListNode* cur2 = list2;
// 创建一个哨兵节点guard，方便操作链表头
guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
tail->next = NULL;
// 合并两个链表
while(cur1 && cur2) {
// 判断当前cur1的值与cur2的值，选择较小的节点
if(cur1->val < cur2->val) {
tail->next = cur1;
cur1 = cur1->next; // 移动cur1指针
tail = tail->next; // 更新tail指针
} else {
tail->next = cur2;
cur2 = cur2->next; // 移动cur2指针
tail = tail->next; // 更新tail指针
}
}
// 如果cur1还有剩余，连接到tail
if(cur1)
tail->next = cur1;
// 如果cur2还有剩余，连接到tail
if(cur2)
tail->next = cur2;
// 头指针是guard的下一个节点
struct ListNode* head = guard->next;
// 释放哨兵节点
free(guard);
return head;
}结语
如果这道题不用哨兵位，你将会被一个错误搞的焦头烂额——对空指针解引用，不相信的话你可以去试试，你一定会影响深刻的。
通过这道题，是不是觉得哨兵位真的很香？非常省事，特别是这种多链表的联合问题，我们一定要留个心眼。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-21，如有侵权请联系 cloudcommunity@tencent 删除遍历链表算法指针数据结构本文标签： 初探数据结构链表OJ算法哨兵位（合并两个有序链表详解）
版权声明：本文标题：【初探数据结构】链表OJ算法——哨兵位（合并两个有序链表详解） 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1748070436a2249054.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论