【数据结构】单链表比第一个元素大的放在前面，其他放在后面

题目

一单链表，以第一个元素为基准，将小于该元素的结点全部放到前面，大于该结点的元素全部放到后面。时间复杂度要求为O(n)，不能申请新空间。

分析

将所有小于第一个元素m的元素移到m前面去，则遍历单链表，比m小的用头插法放到L后面，比m大的则不做改动

解题思路

有几个函数？ 1. 初始化链表 2. 创建单链表 3. 输出单链表 4. 改变单链表（本次程序的关键)

改变单链表函数怎么写？

重复一下，改变单链表函数的功能是：遍历单链表，比第一个元素小的用头插法放到L后面，比m大的则不做改动 。

设置几个指针，用来进行操作：

* p1：指向单链表的第一个结点，用来提取第一个元素的值 * p：当前遍历的结点 * pre：当前遍历节点的前一个结点 * q：当前遍历节点的后一个结点

逻辑思路：

1 先用p1指向单链表的第一个结点

2 pre指向第一个结点，p指向第二个结点，q指向第三个结点，开始遍历

3 如果p->data < p1->data，即当前结点小于第一个元素，用头插法把当前结点移到头结点的后面.

4 如果p->data >= p1->data，即当前结点大于等于第一个元素，则不做改动，pre, p, q继续往后。

具体代码如下：

//初始化省略 while(p){ //遍历单链表 q=p->next; if(p->data < p1->data){ //遇到比第一个元素小的 pre->next = p->next; p->next = L->next; L->next = p; p=q; } else{ //其他则继续往后遍历 pre = p; p = p->next; } }

我的代码

//一单链表，以第一个元素为基准，将小于该元素的结点全部放到前面，大于该结点的元素全部放到后面。 //时间复杂度要求为O(n)，不能申请新空间。 #include<stdio.h> #include<stdlib.h> typedef int Elem; typedef struct Node{ Elem data; struct Node *next; }*Linklist, Node; void Init(Linklist*); //初始化链表 void Create(Linklist); //创建单链表 void output(Linklist); //输出单链表 void change(Linklist); //改变单链表 int main(){ system("color 3F"); Linklist L; //定义单链表 Init(&L); //初始化单链表 printf("\t\t\t请输入单链表L的元素（结束则输入-1）："); Create(L); //创建单链表 printf("\t\t\t此时L单链表元素为："); output(L); change(L); //改变单链表 printf("\t\t\t合并后L单链表元素为："); output(L); } //初始化单链表 void Init(Linklist *L){ //注意此时参数是指针的指针，即指针的地址 *L = (Linklist)malloc(sizeof(Node)); (*L)->next = NULL; } //创建单链表 （尾插法建表） void Create(Linklist L){ //此时参数是单链表的头指针 Node *r, *s; int flag = 1; //设置一个标志，初值为1，当输入-1时，flag为0，建表结束 r = L; // r指针动态指向链表的当前表尾，以便于作尾插入，初值指向头结点 Elem c; //c为要插入的元素值 while(flag){ scanf("%d", &c); if(c!=-1){ s = (Linklist)malloc(sizeof(Node)); //s指针指向要插入的元素。每次都要给s分配空间。 s->data = c; r->next = s; r = s; } else{ flag = 0; r->next = NULL; //将最后一个结点的next链域置为空，表示链表的结束。 } } } //输出链表 void output(Linklist L){ Node *r; r = L->next; while(r){ printf("%d ", r->data); r = r->next; } printf("\n"); } /* 要将所有小于第一个元素m的元素移到m前面去，则遍历单链表，比m小的用头插法放到L后面。其他则不做改动 */ void change(Linklist L){ if(L->next == NULL) return; Node *p, *q, *p1, *pre; p1 = L->next; //p1指向L单链表的第一个元素 p = p1->next; //p指向遍历当前结点 pre = p1; //pre指向当前结点的前一个结点 while(p){ //遍历单链表 q=p->next; if(p->data < p1->data){ //遇到比第一个元素小的 pre->next = p->next; p->next = L->next; L->next = p; p=q; } else{ //其他则继续往后遍历 pre = p; p = p->next; } } }