数据结构 | 每日一练（46）

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-