我们之前学过了无头单向非循环链表的实现,但是我们发现,该链表在尾插的时候有一点不好,就是第一次尾插时,会改变头节点,所以我们在上篇文章实现时传的是二级指针。
而本次所讲哨兵卫单链表在尾插时则不用改变头节点。所谓哨兵卫,其实就是带了一个头节点,该节点不作为用来存储数据。如下:
接下来我们通过具体题目来感受该结构带来的好处。
现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
思路:假如这道题不是一个链表题,而是一个数组题,我相信大家很多人都会想到这么一个办法,开辟两个数组,然后对原数组进行遍历,<x的放在arr1中,剩下的放在arr2中,然后再将arr2合并到arr1中。 对于链表题我们也可以这么来搞,用两个链表分别链接<x以及其余的,最后再合并两个链表。不过这里我们用哨兵卫单链表实现的话,就不需要考虑到链表是否为空的情况。如下:
代码实现:
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
//哨兵卫单链表,两个单链表分别存放<x和>x,最后合并
ListNode* newnode1 = (ListNode*)malloc(sizeof(ListNode));
ListNode* newnode2 = (ListNode*)malloc(sizeof(ListNode));
ListNode* tail1 = newnode1;
ListNode* tail2 = newnode2;
while (pHead) {
//<x的放在newnode1链表
if (pHead->val < x) {
tail1->next = pHead;
tail1 = tail1->next;
}
//>=x的放在newnode2链表
else {
tail2->next = pHead;
tail2 = tail2->next;
}
pHead = pHead->next;
}
//链接两个链表
tail1->next=newnode2->next;
tail2->next=NULL;//一定记得置空!否则又可能出现死循环
struct ListNode*phead=newnode1->next;//保存下一个节点
//释放
free(newnode1);
free(newnode2);
return phead;
}
};
这里我们就不需要考虑链表是否为空的情况,会省很多事,因此对于一些单链表的题目,只要涉及到尾插问题,建议使用带头哨兵卫单链表。并且再次强调,一定要多画图!
这道题,把它想象成一个普通的题,我们应该都会做,即双指针遍历,然后取小尾插。这里需要注意的是,当一方遍历完,另一方没完时,直接将没完的那一方插入即可。这里涉及到尾插,为了不用考虑空表情况下的尾插,我们依然采用哨兵卫单链表。如下:
代码实现:
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
//开辟一个新节点
struct ListNode*newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
newnode->next=NULL;
struct ListNode*tail=newnode;
while(list1 && list2)
{
//取小尾插
if(list1->val < list2->val)
{
tail->next=list1;
tail=tail->next;
list1=list1->next;
}
else
{
tail->next=list2;
tail=tail->next;
list2=list2->next;
}
}
//list2为空
if(list1)
{
tail->next=list1;
}
//list1为空
if(list2)
{
tail->next=list2;
}
//保存头节点的下一个节点
struct ListNode*newhead=newnode->next;
//释放
free(newnode);
return newhead;
}
** 对于需要进行尾插的链表,我们采用带头哨兵卫单链表用来实现尾插,会省事很多,不用考虑空表的存在,不过要注意的是,因为这个哨兵卫节点是我们malloc出来的,所以最后一定记得释放,并且哨兵卫节点的下一个节点才是用来存储有效数据的,另!一定要多画图! **