[数据结构与算法]以X为基准分割链表

以X为基准分割链表

编写程序以x为基准分割链表，使得所有小于x的节点排在大于或等于x的节点之前。如果链表中包含x，x只需出现在小于x的元素之后（如下所示）。分割元素x只需处于“右半部分”即可，其不需要被置于左右两部分之间。

示例:

输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8

下面是C语言完整代码，有空会补思路（其实我的注释已经极其清楚了）

#include<stdio.h>
#include<stdlib.h>
#define len sizeof(struct list)
int n;

struct list
{
    int val;
    struct list *next;
};

struct list *creat()//常规创建一个链表
{
    struct list *head, *p1, *p2;
    p1=p2=(struct list*)malloc(len);//p1,p2现在指向刚开辟的长度为list的内存地址
    scanf("%d",&p1->val);
    head=NULL;
    n=0;
    while(p1->val!=666)//666作为停止标志
    {
        n=n+1;
        if(n==1)
            head=p1;//置头指针
        else
            p2->next=p1;
        p2=p1;
        p1=(struct list*)malloc(len);
        scanf("%d",&p1->val);
    }
    p2->next=NULL;
    return(head);
};


void print(struct list *head)//常规输出一个链表
{
    struct list *p;
    p=head;
    if(head!=NULL)
    {
        do
        {
            printf("%d ",p->val);
            p=p->next;
        }
        while(p!=NULL);
    }
    printf("\n");
}

struct list* partition(struct list* head, int x)
{
    struct list *newhead1=NULL;//这个为寻找小于x的节点开头而设置；
    struct list *newhead2=NULL;//这个为寻找大于X的节点开头而设置；
    struct list *newhead3=NULL;//这个为寻找等于X的节点开头而设置；
    struct list *p=NULL;//p1用来遍历链表；
    struct list *b1=NULL;//b1用来连接小于x的节点；
    struct list *b2=NULL;//b2用来连接大于x的节点；
    struct list *b3=NULL;//b3用来连接等于x的节点；
    p=head;//遍历的开始为链表开头；
    while(p!=NULL)//遍历结束的条件
    {
        if(p->val<x)//开始寻找小于x的节点；
        {
            if(newhead1==NULL)//判断是不是为第一次插入，如果是的话要寻找首地址
            {
                newhead1=p;//找到小于x的首个节点
                b1=newhead1;
            }
            else//不是首次插入就连接节点
            {
                b1->next=p;
                b1=p;
            }
        }
        else if(p->val>x)//开始寻找大于x的节点
        {
            if(newhead2==NULL)//判断是不是为第一次插入，如果是的话要寻找首地址
            {
                newhead2=p;//到小于x的首个节点;
                b2=newhead2;
            }
            else//不是首次插入就连接节点；
            {
                b2->next=p;
                b2=p;
            }
        }
        else if(p->val==x)//开始寻找等于x的节点；
        {
            if(newhead3==NULL)//判断是不是为第一次插入，如果是的话要寻找首地址
            {
                newhead3=p;//找到小于x的首个节点
                b3=newhead3;
            }
            else//不是首次插入就连接节点
            {
                b3->next=p;
                b3=p;
            }
        }
        p=p->next;//p继续向前遍历；
    }
    //以上就将大于，小于，等于x的节点全部连接了起来并且找到了首地址
    //接下来就是连接问题。
    if(newhead1==NULL&&newhead2==NULL)//没大于没小于就返回等于
    {
        b3->next=NULL;
        return(newhead3);
    }
    else if(newhead1!=NULL&&newhead2==NULL)//有小于没大于就就连接小于等于返回小于
    {
        b1->next=newhead3;
        b3->next=NULL;
        return(newhead1);
    }
    else if(newhead1==NULL&&newhead2!=NULL)//有大于没小于就就连接等于大于返回等于
    {
        b3->next=newhead2;
        b2->next=NULL;
        return(newhead3);
    }
    else if(newhead1!=NULL&newhead2!=NULL)//全都有就连接小于等于大于返回小于；
    {
        b1->next=newhead3;
        b3->next=newhead2;
        b2->next=NULL;
        return(newhead1);
    }

}

int main()
{
    struct list *head;
    int n;
    printf("scanf list(stop while here comes 666)\n");
    head=creat();
    printf("scanf judge num:\n");
    scanf("%d",&n);
    head=partition(head,n);
    print(head);
    return 0;
}


//第一次调试出现了死循环，可能是因为三个节点的最后一个指针没有指向NULL;
//经过调试确实是因为没有指向NULL，先已改正。

还记得第一次写链表的时候真是觉得代码好多吗，现在好像也慢慢适应了，写代码如果有了清晰的思路，一会就能写完。