题目描述:
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
解题思路:
创建两个新链表,head1,head2, 遍历原链表,把小于x的结点尾插到head1链表中,把大于等于x的结点尾插到head2链表,最后链接head1和head2,这个题代码实现起来很简单,但是要注意的是几种特殊情况,比如分类后head1为空或head2为空等情况,还需要用if语句单独判断,包括代码中使用结点的next,都需要提前判断一下该结点是否为空,所以我们可以给这两个新链表加上哨兵位,这样就不需要head1,head2就永远不会为空,这样就可以省去很多单独判断语句
简单介绍一下哨兵位:
单链表分为带头结点和不带头结点两种情况。带头结点的第一个节点叫哨兵位，属于附加的链表节点，不保存有效数值，只储存第一个有效节点的地址，负责找到第一个节点。
代码实现:
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {//带哨兵位ListNode* head1,*tail1,*head2,*tail2;head1=tail1=(ListNode*)malloc(sizeof(ListNode));head2=tail2=(ListNode*)malloc(sizeof(ListNode));ListNode* cur=pHead;//小于x的结点尾插到head1,大于x的结点尾插到head2while(cur){if(cur->val<x){tail1->next=cur;tail1=tail1->next;}else {tail2->next=cur;tail2=tail2->next;}cur=cur->next;}//链接两个链表tail1->next=head2->next;tail2->next=NULL;pHead=head1->next;free(head1);free(head2);return pHead;}
};
