单向链表排序函数有有关问题，请大神帮忙看一下！多谢
单向链表排序函数有问题，请大神帮忙看一下！谢谢
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
struct Node *pNext;
}NODE, *PNODE;
//函数声明
PNODE creat_list (void);
void traveal_list (PNODE pHead);
void insert_list (PNODE pHead, int n, int val);//在第n个节点前后加一个
int lenth_list (PNODE pHead);
void sort_list (PNODE pHead);//排序
int main(void)
{
int i;
NODE * pHead = NULL;
pHead = creat_list ();
traveal_list(pHead);
insert_list(pHead, 2, 22);
traveal_list(pHead);
i = lenth_list (pHead);
printf("链表的长度是%d", i);
sort_list(pHead);
traveal_list(pHead);
return 0;
}
//定义函数
PNODE creat_list (void)
{
int val;//用来存放用户临时输入的值
int len;//用来存放用户输入的结点个数
int i;
PNODE pHead = (PNODE)malloc(sizeof(NODE));
if (!pHead){printf("内存分配失败");exit (-1);}
pHead->pNext = NULL;
PNODE q;
q = pHead;
q->pNext = NULL;
printf("请输入您要建立的结点个数：Len = ");
scanf("%d", &len);
for (i = 0; i < len; i++)
{
printf("请输入第i+1个结点的值：val = ");
scanf("%d", &val);
PNODE p = (PNODE)malloc(sizeof(NODE));//必须在这里进行定义分配内存
if (!p){printf("内存分配失败");exit (-1);}
p->data = val;
p->pNext = NULL;
q->pNext = p;
q = p;
}
return pHead;
}
void traveal_list (PNODE pHead)
{
PNODE p;
if(pHead->pNext == NULL){printf("这是一个空链表");exit (-1);}
p = pHead->pNext;
if (!p){printf("内存分配失败");exit (-1);}
while (p)
{
printf("%d ", p->data);
p = p->pNext;
}
puts("\n");
return;
}
void insert_list (PNODE pHead, int n, int val)
{
int i;
PNODE p = pHead;
PNODE q=(PNODE)malloc(sizeof(NODE));
if (!q){printf("内存分配失败");exit (-1);}
for (i= 0; i < n-1; i++)
{
p = p->pNext;
}
q->data = val;
q->pNext = p->pNext;
p->pNext = q;
}
int lenth_list (PNODE pHead)
{
int count = 0;
PNODE p = pHead->pNext;
while (p){count++;p = p->pNext;}
return count;
}
void sort_list (PNODE pHead)
{
PNODE p, q,n;
n = NULL;
p = pHead;
q = p->pNext;
do{
do{
if (q->data > q->pNext->data)
{
p->pNext =q->pNext;
q->pNext = q->pNext->pNext;
p->pNext->pNext = q;
}
p = p->pNext;
q = p->pNext;
}while (q != n);
n = p;
p = pHead;
q = p->pNext;
}while (p->pNext != n);
}
------解决思路----------------------
为何排序时不用while，或for。而且do while，当 q = p->pNext;= null时，q->data就会崩溃
p->pNext =q->pNext;
q->pNext = q->pNext->pNext;
p->pNext->pNext = q;
这是什么意思，楼主你画图看看，是否能达到你要的结果，
------解决思路----------------------
仅供参考：
------解决思路----------------------
再供参考：
------解决思路----------------------
供楼主参考
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
struct Node *pNext;
}NODE, *PNODE;
//函数声明
PNODE creat_list (void);
void traveal_list (PNODE pHead);
void insert_list (PNODE pHead, int n, int val);//在第n个节点前后加一个
int lenth_list (PNODE pHead);
void sort_list (PNODE pHead);//排序
int main(void)
{
int i;
NODE * pHead = NULL;
pHead = creat_list ();
traveal_list(pHead);
insert_list(pHead, 2, 22);
traveal_list(pHead);
i = lenth_list (pHead);
printf("链表的长度是%d", i);
sort_list(pHead);
traveal_list(pHead);
return 0;
}
//定义函数
PNODE creat_list (void)
{
int val;//用来存放用户临时输入的值
int len;//用来存放用户输入的结点个数
int i;
PNODE pHead = (PNODE)malloc(sizeof(NODE));
if (!pHead){printf("内存分配失败");exit (-1);}
pHead->pNext = NULL;
PNODE q;
q = pHead;
q->pNext = NULL;
printf("请输入您要建立的结点个数：Len = ");
scanf("%d", &len);
for (i = 0; i < len; i++)
{
printf("请输入第i+1个结点的值：val = ");
scanf("%d", &val);
PNODE p = (PNODE)malloc(sizeof(NODE));//必须在这里进行定义分配内存
if (!p){printf("内存分配失败");exit (-1);}
p->data = val;
p->pNext = NULL;
q->pNext = p;
q = p;
}
return pHead;
}
void traveal_list (PNODE pHead)
{
PNODE p;
if(pHead->pNext == NULL){printf("这是一个空链表");exit (-1);}
p = pHead->pNext;
if (!p){printf("内存分配失败");exit (-1);}
while (p)
{
printf("%d ", p->data);
p = p->pNext;
}
puts("\n");
return;
}
void insert_list (PNODE pHead, int n, int val)
{
int i;
PNODE p = pHead;
PNODE q=(PNODE)malloc(sizeof(NODE));
if (!q){printf("内存分配失败");exit (-1);}
for (i= 0; i < n-1; i++)
{
p = p->pNext;
}
q->data = val;
q->pNext = p->pNext;
p->pNext = q;
}
int lenth_list (PNODE pHead)
{
int count = 0;
PNODE p = pHead->pNext;
while (p){count++;p = p->pNext;}
return count;
}
void sort_list (PNODE pHead)
{
PNODE p, q,n;
n = NULL;
p = pHead;
q = p->pNext;
do{
do{
if (q->data > q->pNext->data)
{
p->pNext =q->pNext;
q->pNext = q->pNext->pNext;
p->pNext->pNext = q;
}
p = p->pNext;
q = p->pNext;
}while (q != n);
n = p;
p = pHead;
q = p->pNext;
}while (p->pNext != n);
}
------解决思路----------------------
为何排序时不用while，或for。而且do while，当 q = p->pNext;= null时，q->data就会崩溃
p->pNext =q->pNext;
q->pNext = q->pNext->pNext;
p->pNext->pNext = q;
这是什么意思，楼主你画图看看，是否能达到你要的结果，
------解决思路----------------------
仅供参考：
//带表头结点的单向链表
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
struct NODE {
int data;
struct NODE *next;
} H,*head,*p,*q,*s1,*s2,*s3,*s4,*s;
int i,j,k,n,t,m;
int main() {
srand(time(NULL));
//填写头节点数据
H.data=-1;
H.next=NULL;
head=&H;
//创建10个节点的单链表
p=head;
for (i=0;i<10;i++) {
q=(struct NODE *)malloc(sizeof(struct NODE));
if (NULL==q) return 1;
q->data=rand()%100;//填写0..99的随机值
q->next=NULL;
p->next=q;
p=q;
}
//输出整个单链表
s=head->next;
while (1) {
if (NULL==s) {
printf("\n");
break;
}
printf("%02d->",s->data);
s=s->next;
}
//将值为5的结点插入到单链表的第k个结点前
k=3;
n=0;
p=head;
while (1) {
if (NULL==p) {
break;
}
n++;
if (k==n) {
q=(struct NODE *)malloc(sizeof(struct NODE));
if (NULL==q) return 1;
q->data=5;
q->next=p->next;
p->next=q;
break;
}
p=p->next;
}
//输出整个单链表
s=head->next;
while (1) {
if (NULL==s) {
printf("\n");
break;
}
printf("%02d->",s->data);
s=s->next;
}
//删除第k个节点
k=5;
n=0;
p=head;
while (1) {
if (NULL==p) {
break;
}
n++;
if (k==n) {
q=p->next;
if (q) {
p->next=q->next;
free(q);
}
break;
}
p=p->next;
}
//输出整个单链表
s=head->next;
while (1) {
if (NULL==s) {
printf("\n");
break;
}
printf("%02d->",s->data);
s=s->next;
}
//从小到大排序
for (p=head;p!=NULL && p->next!=NULL;p=p->next) {
for (q=p->next;q!=NULL && q->next!=NULL;q=q->next) {
if (p->next->data > q->next->data) {
//交换data
// printf("swap %02d %02d\n",p->next->data,q->next->data);
// t=p->next->data;p->next->data=q->next->data;q->next->data=t;
//或者
//交换next
// printf("swap %02d %02d\n",p->next->data,q->next->data);
s1=p->next;
s2=p->next->next;
s3=q->next;
s4=q->next->next;
if (s2!=s3) {
p->next=s3;
s3->next=s2;
q->next=s1;
s1->next=s4;
} else {
p->next=s3;
s3->next=s1;
q=s3;
s1->next=s4;
}
//输出整个单链表
// s=head->next;
// while (1) {
// if (NULL==s) {
// printf("\n");
// break;
// }
// printf("%02d->",s->data);
// s=s->next;
// }
// getchar();
}
}
}
//输出整个单链表
s=head->next;
while (1) {
if (NULL==s) {
printf("\n");
break;
}
printf("%02d->",s->data);
s=s->next;
}
//将单链表中前 m 个结点和后 n 个结点进行互换,m+n为链表总长10
m=4;
n=6;
k=0;
p=head;
while (1) {
if (NULL==p) {
break;
}
k++;
if (m+1==k) {
q=p;
}
s=p;
p=p->next;
}
s1=head->next;
head->next=q->next;
s->next=s1;
q->next=NULL;
//输出整个单链表
s=head->next;
while (1) {
if (NULL==s) {
printf("\n");
break;
}
printf("%02d->",s->data);
s=s->next;
}
//释放所有节点
p=head->next;
while (1) {
if (NULL==p) {
break;
}
q=p->next;
free(p);
p=q;
}
return 0;
}
//18->94->58->17->27->20->43->57->75->78->
//18->94->05->58->17->27->20->43->57->75->78->
//18->94->05->58->27->20->43->57->75->78->
//05->18->20->27->43->57->58->75->78->94->
//43->57->58->75->78->94->05->18->20->27->
//
------解决思路----------------------
再供参考：
//不带表头结点的单向链表
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#include <locale.h>
struct NODE {
int data;
struct NODE *next;
} *head,*p,*q,*s,*p1,*p2,*q1,**ta;
int i,k,n,t,m,v,N=10;
int main() {
setlocale(LC_ALL,"chs");
srand(time(NULL));
head=NULL;
printf("创建%d个节点的单链表:",N);//创建N个节点的单链表
p=head;
for (i=0;i<N;i++) {
q=(struct NODE *)malloc(sizeof(struct NODE));
if (NULL==q) exit(1);
q->data=rand()%100;//填写0..99的随机值
q->next=NULL;
if (NULL==p) {
head=q;
p=head;
} else {
p->next=q;
p=q;
}
}
//输出整个单链表
s=head;
while (1) {
if (NULL==s) {
printf("\n");
break;
}
printf("%02d->",s->data);
s=s->next;
}
k=3;
v=5;
printf("将值为%d的结点插入到单链表的第%d个结点前:",v,k);//将值为v的结点插入到单链表的第k个结点前
n=0;
p=head;
while (1) {
if (NULL==p) {
break;
}
n++;
if (k==1) {
q=(struct NODE *)malloc(sizeof(struct NODE));
if (NULL==q) exit(1);
q->data=5;
q->next=head;
head=q;
break;
} else {
if (k-1==n) {
q=(struct NODE *)malloc(sizeof(struct NODE));
if (NULL==q) exit(1);
q->data=5;
q->next=p->next;
p->next=q;
break;
}
}
p=p->next;
}
//输出整个单链表
s=head;
while (1) {
if (NULL==s) {
printf("\n");
break;
}
printf("%02d->",s->data);
s=s->next;
}
k=5;
printf("删除第%d个节点:",k);//删除第k个节点
n=0;
p=head;
while (1) {
if (NULL==p) {
break;
}
n++;
if (k==1) {
q=head;
head=head->next;
free(q);
break;
} else {
if (k-1==n) {
q=p->next;
if (q) {
p->next=q->next;
free(q);
}
break;
}
}
p=p->next;
}
//输出整个单链表
s=head;
while (1) {
if (NULL==s) {
printf("\n");
break;
}
printf("%02d->",s->data);
s=s->next;
}
printf("从小到大排序:");//从小到大排序
for (p=head,p1=NULL;p!=NULL;p1=p,p=p->next) {
for (q=p->next,q1=p;q!=NULL;q1=q,q=q->next) {
if (p->data > q->data) {
//交换data
// printf("swap %02d %02d\n",p->data,q->data);
// t=p->data;p->data=q->data;q->data=t;
//或者
//交换next
// printf("swap %02d %02d\n",p->data,q->data);
if (p==head) {//p是头
if (p->next==q) {//pq挨着
head=q;
p->next=q->next;
q->next=p;
q=p;
p=head;
} else {//pq不挨着
head=q;
p2=p->next;
p->next=q->next;
q->next=p2;
q1->next=p;
q=p;
p=head;
}
} else {//p不是头
if (p->next==q) {//pq挨着
p1->next=q;
p->next=q->next;
q->next=p;
q=p;
p=p1->next;
} else {//pq不挨着
p1->next=q;
p2=p->next;
p->next=q->next;
q->next=p2;
q1->next=p;
q=p;
p=p1->next;
}
}
//输出整个单链表
// s=head;
// while (1) {
// if (NULL==s) {
// printf("\n");
// break;
// }
// printf("%02d->",s->data);
// s=s->next;
// }
// getchar();
}
}
}
//输出整个单链表并计算链表长度n
n=0;
s=head;
while (1) {
if (NULL==s) {
printf("\n");
break;
}
printf("%02d->",s->data);
n++;
s=s->next;
}
printf("将整个链表逆序:");//将整个链表逆序
if (n>=2) {
ta=(struct NODE **)malloc(n*sizeof(struct NODE *));
if (NULL==ta) exit(1);
s=head;
for (i=0;i<n;i++) {
ta[i]=s;
s=s->next;
}
head=ta[n-1];
for (i=n-1;i>0;i--) {
ta[i]->next=ta[i-1];
}
ta[0]->next=NULL;
free(ta);
}
//输出整个单链表
s=head;
while (1) {
if (NULL==s) {
printf("\n");
break;
}
printf("%02d->",s->data);
s=s->next;
}
m=4;
n=6;
printf("将单链表中前%d个结点和后%d个结点进行互换:",m,n);//将单链表中前m个结点和后n个结点进行互换,m+n为链表总长
k=0;
p=head;
while (1) {
if (NULL==p) {
break;
}
k++;
if (m==k) {
q=p;
}
s=p;
p=p->next;
}
q1=head;
head=q->next;
s->next=q1;
q->next=NULL;
//输出整个单链表
s=head;
while (1) {
if (NULL==s) {
printf("\n");
break;
}
printf("%02d->",s->data);
s=s->next;
}
//释放所有节点
p=head;
while (1) {
if (NULL==p) {
break;
}
q=p->next;
free(p);
p=q;
}
return 0;
}
//创建10个节点的单链表:08->74->07->23->03->99->31->56->88->16->
//将值为5的结点插入到单链表的第3个结点前:08->74->05->07->23->03->99->31->56->88->16->
//删除第5个节点:08->74->05->07->03->99->31->56->88->16->
//从小到大排序:03->05->07->08->16->31->56->74->88->99->
//将整个链表逆序:99->88->74->56->31->16->08->07->05->03->
//将单链表中前4个结点和后6个结点进行互换:31->16->08->07->05->03->99->88->74->56->
//
------解决思路----------------------
供楼主参考
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode sortList(ListNode head) {
if ((null == head)
------解决思路----------------------
(null == head.next)) {
return head;
}
ListNode[] list = divideList(head);
list[0] = sortList(list[0]);
list[1] = sortList(list[1]);
return mergeList(list[0], list[1]);
}
private ListNode[] divideList(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while ((null != fast.next) && (null != fast.next.next)) {
slow = slow.next;
fast = fast.next.next;
}
ListNode[] list = new ListNode[2];
list[0] = head;
list[1] = slow.next;
slow.next = null;
return list;
}
private ListNode mergeList(ListNode headA, ListNode headB) {
if (null == headA) {
return headB;
} else if (null == headB) {
return headA;
}
ListNode head = null;
ListNode tail = null;
while ((null != headA) && (null != headB)) {
ListNode node = null;
if (headA.val < headB.val) {
node = headA;
headA = node.next;
} else {
node = headB;
headB = node.next;
}
node.next = null;
if (null == head) {
head = node;
tail = node;
} else {
tail.next = node;
tail = node;
}
}
if (null != headA) {
tail.next = headA;
} else if (null != headB) {
tail.next = headB;
}
return head;
}
}