數(shù)據(jù)結構：單鏈表的排序

給定一個單鏈表的頭結點head（該結點有值），長度為n的無序單鏈表，對其按升序排序后，返回新鏈表。如當輸入鏈表 {3,1,4,5,2} 時，經升序排列后，原鏈表變?yōu)?{1,2,3,4,5}，對應的輸出為 {1,2,3,4,5}。

代碼實現(xiàn)

C語言代碼：

structListNode*sortInList(structListNode*head){
if(head==NULL)
returnNULL;
//添加一個頭指針，指向head，方便后面的排序
structListNode*H;
H=malloc(sizeof(structListNode));
H->next=head;
//第一步：定義三個指針
structListNode*p,*q,*r;
//第二步：將p指向head，并將頭指針斷開鏈接
p=H->next;
H->next=NULL;
//遍歷鏈表
while(p)
{
//第三步：q指向當前要操作的結點，p后移，r指向頭指針
q=p;
p=p->next;
r=H;
//第四步：將r的后繼數(shù)值與當前操作結點q的值進行比較
//若條件成立，r后移一個位置后，繼續(xù)進行比較
//若條件不成立，跳出while循環(huán)，將q指向r的后繼，r的后繼指向q
while(r->next&&r->next->valval)
r=r->next;
q->next=r->next;
r->next=q;
}
//第五步：返回頭指針H的后繼結點鏈表
returnH->next;
}

圖解代碼

第一步：定義三個指針

第二步：將p指向head，并將頭指針斷開鏈接

第三步：q指向當前要操作的結點，p后移，r指向頭指針

第四步：將r的后繼數(shù)值與當前操作結點q的值進行比較：若條件成立，r后移一個位置后，繼續(xù)進行比較；若條件不成立，跳出while循環(huán)，將q指向r的后繼，r的后繼指向q

第五步：返回頭指針H的后繼結點鏈表

審核編輯：湯梓紅