給定一個(gè)單鏈表的頭結(jié)點(diǎn)head（該結(jié)點(diǎn)有值），長(zhǎng)度為n的無序單鏈表，對(duì)其按升序排序后，返回新鏈表。如當(dāng)輸入鏈表 {3,1,4,5,2} 時(shí)，經(jīng)升序排列后，原鏈表變?yōu)?{1,2,3,4,5}，對(duì)應(yīng)的輸出為 {1,2,3,4,5}。

代碼實(shí)現(xiàn)

C語言代碼：

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

圖解代碼

第一步：定義三個(gè)指針

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

第三步：q指向當(dāng)前要操作的結(jié)點(diǎn)，p后移，r指向頭指針

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

第五步：返回頭指針H的后繼結(jié)點(diǎn)鏈表

審核編輯：湯梓紅