数据结构与算法
9 篇文章3 订阅
深窥自己的心，而后发觉一切的奇迹在你自己
往期回顾：
链表刷题常用技巧——快慢指针
【LeetCode】单链表——刷题
数据结构——单链表
目录
合并两个有序链表
思路及图解
需要额外注意的问题
核心代码
链表分割
思路及图解
核心代码
大家好，我是纪宁。这篇文章向大家介绍单链表刷题阶段常用的思路——构建哨兵位。
单链表分为带头节点和不带头节点两种。带头结点的单链表的第一个节点，也叫哨兵位，属于附加的链表节点，无有效数值，只储存第一个有效节点的地址，负责找到第一个节点。
那么，如何构造哨兵位来简化OJ题，这是我们需要思考的问题。
众所周知，在面试题、笔试题、竞赛题以及我们通常做的 LeetCode 练习题中，题目中给的单链表都是没有哨兵位的，而如果我们要进行单链表的头插、头删或者新创建节点进行操作，都是非常复杂的，通常还要改变头指针的指向，并对特别麻烦的边界进行考虑。
虽然在众多OJ题中都没有哨兵位，那么我们可以考虑手动构建开辟一个或多个哨兵位的空间，有了哨兵位后，对新创建的链表进行操作的时候，第一步只需要尾插即可。
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
例如：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4】
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
思路及图解
将两个链表的节点逐个比较，小的尾插到新链表的后面，每次尾插完，新链表和较小值的链表的指针都要向前走，有一个为空就停止循环，最后再将那个不为空的链表节点全部尾插到新链表。
需要额外注意的问题
要考虑一个链表为空的情况
因为要尾插到新链表，所以要额外开辟一个哨兵位的空间，可以方便连续尾插，因为这样就可以不用改变头指针的指向。
要及时释放哨兵位的空间
在循环结束后要将没有遍历结束的链表继续尾插到新链表后面
核心代码
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode *head,*tail;
head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
if(list1==NULL)
return list2;
if(list2==NULL)
return list1;
while(list1&&list2)
{
if(list1->val<list2->val)
{
tail->next=list1;
list1=list1->next;
tail=tail->next;
}
else
{
tail->next=list2;
list2=list2->next;
tail=tail->next;
}
}
while(list1)
{
tail->next=list1;
list1=list1->next;
tail=tail->next;
}
while(list2)
{
tail->next=list2;
list2=list2->next;
tail=tail->next;
}
struct ListNode *del=head->next;
free(head);
return del;
}
链表分割
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
如图，给定的链表为 4-5-3-1-2-7 ，给一定值为 3，分割后的值为 1-2-4-5-3-7
思路及图解
创建两个带哨兵位的链表，分别存放值小于x的节点和值大于x的节点，将数据全部存放在这两个新链表之后，再将小于 x 的那个链表的尾节点指向 大于 x 的那个链表的第一个有效节点，最后将大于 x 的链表的尾节点的 next 置空。
核心代码
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
ListNode*tail2,*cur2,*tail1,*cur1;//哨兵位
tail1=cur1=(ListNode*)malloc(sizeof(ListNode));//小于x的
tail2=cur2=(ListNode*)malloc(sizeof(ListNode));//大于x的
while(pHead)
{
if(pHead->val<x)
{
cur1->next=pHead;
cur1=cur1->next;
}
else
{
cur2->next=pHead;
cur2=cur2->next;
}
pHead=pHead->next;
}
cur1->next=tail2->next;
cur2->next=NULL;
ListNode *del=tail1->next;
free(tail1);
free(tail2);
return del;
}
};
需要注意：cur2->next必须要置空，否则就可能出现成环而无法结束的情况。
