全部
博文收录
Ada助手
问答

请教面试题--链表实现的归并排序

xiaotry1986 2007-12-10 01:00:41

前两天去笔试，碰到一个链表实现归并排序的题目，没做出来，请大侠指导

题目大概是这样，两个函数，第一个是对两个已经排好序的链表归并，第二个是主函数，入参为待排序链表，调用第一个函数。
struct node
{
int value;
node * next;
};

node * merge(node * first, node * second)
{ //对两个已经排好序的链表进行归并
node * head = new node;
node * current;
current = head;
while(first != NULL && second !=NULL)
{
if(first->value < second->value)
{
current->next = first;
first = first->next;
current = current->next;
}
else{
current->next = second;
second = second->next;
current = current->next;
}
}
//把最后剩下的项加到最后面
while(first != NULL)
{
current->next = first;
first = first->next;
current = current->next;
}
while(second != NULL)
{
current->next = second;
second = second->next;
current = current->next;
}

return head->next;
}

node * mergeSort(node * toSortList)
{
node * first = toSortList;
node * second = toSortList->next;

if(first == NULL or second == NULL) return toSortList;

while(second != NULL && second->next != NULL)
{
toSortList = toSortList->next;
second =
}

toSortList =
second =

return merge( , );
}

上面缺的地方是要填的，顺序可能有点误差，不太记得了，不好意思。希望有达人能够帮忙解决，不甚感激。
QQ：357016518

...全文

给本帖投票

用AI写文章

3 条回复

切换为时间正序

请发表友善的回复…

发表回复

xiaotry1986 2007-12-28

打赏
举报

感觉zhulinpptor的方法像是插入排序，我开始也是这么想的.不过如果这样做的话就不需要用toSortList，直接用second = second -> next;就可以获取最后一个元素。

dlyme 的方法我看懂了，利用不一样的步长，将原来的链表分成两个长度差不多的子链表，将其排序后归并。这种做法应该就是出题者的本意，真正用递归+归并的方法解决问题，小弟佩服加感激，无以为报，送上一点薄分~~

大王派我去巡山 2007-12-18

打赏
举报

楼主有两句话顺序确实是颠倒了。
ls在分数组的时候将大小为n的数组总是固定分成了n-1,1，只对前一部分归并，效率低了些。觉得应该是这样：



node*  mergeSort(node*  toSortList) 

{ 

	node* first;

    node* second;

    first  = toSortList; 

    second = toSortList->next; 



    if(first == NULL || second == NULL) return toSortList; 



    while(second != NULL && second->next != NULL) 

	{ 

        toSortList = toSortList-> next; 

        second =  second->next->next;  //填空

	} 



	second = toSortList->next;  //填空

    toSortList->next = NULL;    //填空



	return   merge(mergeSort(first), mergeSort(second)); 

}

测试通过

pptor 2007-12-18

打赏
举报

//第二个函数
node *mergeSort(node *toSortList)
{
node *first=toSortList;
node *second=toSortList->next;
if(!first||!second)return toSortList;
while(!second&&!second->next){
toSortList=toSortList->next;
second=toSortList->next}//填空
toSortList=NULL; //填空
// second=; //这里不需要填
return merge(mergeSort(first),second);//填空
}