Question

C++单向链表冒泡排序

#include<iostream>
using namespace std;
struct Node
{int data;
Node *next;
};
Node* sort(Node* head)
{
Node* tail = NULL;

while(tail != head->next)
{
Node* pre = head;
Node* cur = head->next;
if(head->data > head->next->data)//因为链首没有前一个结点，所以单独出来讨论
{head=head->next;
head->next=pre;
head->next->next=cur->next;
pre=head;
cur=pre->next;
}
while(cur != tail && cur->next != tail)
{

if( cur->data > cur->next->data )
{
//交换当前节点和后一个节点
pre->next = cur->next;
cur->next = cur->next->next;
pre->next->next = cur;
}
pre = pre->next;
cur = pre->next;
} tail = cur;
}
return head;
}
int main()
{int n,i,data2;
cin>>n;
Node *head,*p,*q;
head=NULL;
for(i=1;i<=n;i++)
{cin>>data2;
p=new Node;
p->data=data2;
p->next=NULL;
if(head==NULL)
head=p;
else q->next=p;
q=p;
}
q=sort(head);
while(q)
{cout<<q->data<<" ";
q=q->next;
}
return 0;
}
为什么我输入5 3 2 1 6 5 没有输出
如果我把这一段删除
if(head->data > head->next->data)//因为链首没有前一个结点，所以单独出来讨论
{head=head->next;
head->next=pre;
head->next->next=cur->next;
pre=head;
cur=pre->next;
}
又有了输出，但是只是出了链首以外的数的排序的输出，要崩溃了，求教

Answer 1

head=head->next;

当头结点比较大的时候，你每排一次序，头结点的位置都被改变。
应该每次重新设置一下head.

追问

在哪里重新设置一下head，而且我是冒泡排序啊，头结点不要往后移啊，只是最后的tail结点往前移而已，我的if里不是也改了head结点了吗

追答

不好意思，是我看错了。
但是这段话还是有问题的，
head=head->next;
head->next=pre;//此时链表已断并且head指向pre，pre指向head
head->next->next=cur->next;//等价于 pre->next=cur->next 即第一个节点pre
也就是说，到最后pre->next=pre;整个链表只有一个元素。循环也无法跳出。
这段话应该这么写：
head->next=cur->next;
cur->next=head;

追问

终于明白了啊，一旦链表指向发生改变，就要小心。
你那个还是不对啊，应该是
head->next=cur->next;
head=cur;
head->next=pre;
不过还是太感谢了