C++ 单链表排序：将负数、零和正数节点分别移动到链表头部、中间和尾部

#include <malloc.h>
#include <stdio.h>
#include<iostream>
using namespace std;
const int MAXSIZE=100;
typedef int ElemType;
typedef struct node
{	ElemType data;					//数据域
	struct node *next;				//指针域
} SLinkNode;						//单链表结点类型
void InitList(SLinkNode *&L)					//初始化单链表L
{	L=(SLinkNode *)malloc(sizeof(SLinkNode));	//创建头结点L
	L->next=NULL;
}
void DestroyList(SLinkNode *&L)		//销毁单链表L
{	SLinkNode *pre=L,*p=pre->next;
	while (p!=NULL)
	{	free(pre);
		pre=p; p=p->next;			//pre、p同步后移
	}
	free(pre);
}
int GetLength(SLinkNode *L)			//求长度
{	int i=0;
	SLinkNode *p=L->next;
	while (p!=NULL)
	{	 i++;
		p=p->next;
	}
	return i;
}
int GetElem(SLinkNode *L,int i,ElemType &e)	//求第i个结点值
{	int j=0;
	SLinkNode *p=L;					//p指向头结点，计数器j置为0
	if (i<=0) return 0;				//参数i错误返回0
	while (p!=NULL && j<i)
	{	 j++;
		p=p->next;
	}
	if (p==NULL)
		return 0;					//未找到返回0
	else
	{	 e=p->data;
		return 1;					//找到后返回1
	}
}
int Locate(SLinkNode *L,ElemType e)	//求第一个值为e的结点位置
{	SLinkNode *p=L->next;
	int j=1;						//p指向第一个数据结点，j置为其序号1
	while (p!=NULL && p->data!=e)
	{	 p=p->next;
		j++;
	}
	if (p==NULL) return(0);			//未找到返回0
	else return(j);					//找到后返回其序号
}
int InsElem(SLinkNode *&L,ElemType x,int i)	//插入结点值为x的结点
{	int j=0;
	SLinkNode *p=L,*s;
	if (i<=0) return 0;				//参数i错误返回0
	while (p!=NULL && j<i-1)		//查找第i-1个结点p
	{	 j++;
		p=p->next;
	}
	if (p==NULL)
		return 0;					//未找到第i-1个结点时返回0
	else							//找到第i-1个结点p
	{	 s=(SLinkNode *)malloc(sizeof(SLinkNode));
		s->data=x;					//创建存放元素x的新结点s
		s->next=p->next;			//将s结点插入到p结点之后
		p->next=s;
		return 1;					//插入运算成功,返回1
	}
}
int DelElem(SLinkNode *&L,int i)	//删除结点
{	int j=0;
	SLinkNode *p=L,*q;
	if (i<=0) return 0;				//参数i错误返回0
	while (p!=NULL && j<i-1)		//查找第i-1个结点
	{	 j++;
		p=p->next;
	}
	if (p==NULL)
		return 0;					//未找到第i-1个结点时返回0
	else							//找到第i-1个结点p
	{	 q=p->next;					//q指向被删结点
		if (q==NULL)
			return 0;				//没有第i个结点时返回0
		else
		{	 p->next=q->next;		//从单链表中删除q结点
			free(q);				//释放其空间
			return 1;
		}
	}
}
void DispList(SLinkNode *L)			//输出单链表
{	SLinkNode *p=L->next;
	while (p!=NULL)
	{	 printf('%d ',p->data);
		p=p->next;
	}
	printf('
');
}

void CreateListF(SLinkNode *&L,ElemType a[],int n)	//头插法建表
{	SLinkNode *s;  int i;
	L=(SLinkNode *)malloc(sizeof(SLinkNode));		//创建头结点
	L->next=NULL;									//头结点的next域置空
	for (i=0;i<n;i++)								//遍历a数组所有元素
	{	 s=(SLinkNode *)malloc(sizeof(SLinkNode));
		s->data=a[i];								//创建存放a[i]元素的新结点s
		s->next=L->next;							//将s插在头结点之后
		L->next=s;
	}
}

void CreateListR(SLinkNode *&L,ElemType a[],int n)	//尾插法建表
{	SLinkNode *s,*tc;  int i;
	L=(SLinkNode *)malloc(sizeof(SLinkNode));		//创建头结点
	tc=L;											//tc为L的尾结点指针
	for (i=0;i<n;i++)
	{	 s=(SLinkNode *)malloc(sizeof(SLinkNode));
		s->data=a[i];								//创建存放a[i]元素的新结点s
		tc->next=s;									//将s结点插入tc结点之后
		tc=s;
	}
	tc->next=NULL;									//尾结点next域置为NULL
}

//补充代码
// 在此处补充你的代码
void Move(SLinkNode *&L) {
    SLinkNode *negative = NULL;  // 负数节点的头指针
    SLinkNode *zero = NULL;  // 0节点的头指针
    SLinkNode *positive = NULL;  // 正数节点的头指针
    SLinkNode *p = L->next;  // 当前节点指针
    SLinkNode *q;  // 用于保存下一个节点指针

    while (p != NULL) {
        q = p->next;  // 保存下一个节点指针

        if (p->data < 0) {
            p->next = negative;  // 将当前节点插入到负数节点的头部
            negative = p;
        } else if (p->data == 0) {
            p->next = zero;  // 将当前节点插入到0节点的头部
            zero = p;
        } else {
            p->next = positive;  // 将当前节点插入到正数节点的头部
            positive = p;
        }

        p = q;  // 移动到下一个节点
    }

    // 将负数节点、0节点和正数节点连接在一起
    L->next = negative;
    if (negative != NULL) {
        p = negative;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = zero;
    } else {
        L->next = zero;
    }
    if (zero != NULL) {
        p = zero;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = positive;
    } else {
        L->next = positive;
    }
}

int main()
{
	SLinkNode *L;
	int n;
	ElemType a[MAXSIZE];
	cin>>n;
	for(int i=0;i<n;i++)
	   cin>>a[i];
	CreateListR(L,a,n);				//尾插法建表
	Move(L);
    DispList(L);
	DestroyList(L);
	return 0; 
}

输入

13
6 4 -6 -4 0 1 0 -2 2 0 3 -3 -5

输出

-6 -4 -2 -3 -5 0 0 0 6 4 1 2 3

样例输入

13
6 4 -6 -4 0 1 0 -2 2 0 3 -3 -5

样例输出

-6 -4 -2 -3 -5 0 0 0 6 4 1 2 3

代码解释

创建三个指针 negative、zero 和 positive 分别指向负数节点、0 节点和正数节点的头部。
遍历链表，将每个节点根据其数据值插入到相应的链表头部。
连接三个链表，将 negative、zero 和 positive 按照顺序连接起来，并将头结点 L 的 next 指针指向 negative。

算法复杂度

该算法的时间复杂度为 O(n)，空间复杂度为 O(1)，其中 n 为链表的长度。