1
每日一练
1．已知不带头结点的线性链表 list，链表中结点构造为（data、link），其中 data 为数据域，link 为指
针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。
正确答案
ps：||代表注释
1．[题目分析]本题实质上是一个排序问题，要求“不得使用除该链表结点以外的任何链结点空间”。链表上的排序采用直接插入排序比较方便，即首先假定第一个结点有序，然后，从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。
LinkedList LinkListSort(LinkedList list)∥list是不带头结点的线性链表，链表结点构造为data和link两个域，data是数据域，link是指针域。本算法将该链表按结点数据域的值的大小，从小到大重新链接。
{p=list->link; ∥p是工作指针，指向待排序的当前元素。
list->link=null;∥假定第一个元素有序，即链表中现只有一个结点。
while(p!=null)
{r=p->link; ∥r是p的后继。
q=list;
if(q->data>p->data)∥处理待排序结点p比第一个元素结点小的情况。
{p->link=list;
list=p;∥链表指针指向最小元素。
}
else∥查找元素值最小的结点。
{ while(q->link!=null&&q->link->data<p->data)q=q->link;
p->link=q->link;∥将当前排序结点链入有序链表中。
q->link=p; }
p=r;∥p指向下个待排序结点。
}
}
[算法讨论]算法时间复杂度的分析与用顺序存储结构时的情况相同。但顺序存储结构将第i(i>1)个元素插入到前面第1至第i-1个元素的有序表时，是将第i个元素先与第i-1个元素比较。而在链表最佳情况均是和第一元素比较。两种存储结构下最佳和最差情况的比较次数相同，在链表情况下，不移动元素，而是修改结点指针。另一说明是，本题中线性链表list不带头结点，而且要求“不得使用除该链表以外的任何链结点空间“，所以处理复杂，需要考虑当前结点元素值比有序链表第一结点的元素值还小的情况，这时要修改链表指针list。如果list是头结点的指针，则相应处理要简单些，其算法片段如下：
p=list->link;∥p指向第一元素结点。
list->link=null;∥有序链表初始化为空
while(p!=null)
{r=p->link;∥保存后继
q=list;
while(q->link!=null && q->link->data<p->data)q=q->link;
p->link=q->link;
q->link=p;
q=r;
}
如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！
-end-