网站运营建设方案,asp 网站建设教程,仿我喜欢网站源码免费,做运营那些无版权图片网站文章目录排序链表二、解题思路#xff1a;二.实现的代码总结#xff1a;排序链表
一道链表排序题#xff0c;链接在这里 二、解题思路#xff1a;
解题思路#xff1a;使用归并排序#xff08;用递归实现#xff09;
第一步#xff1a;先找到链表的中间节点
第二步…
文章目录排序链表二、解题思路二.实现的代码总结排序链表
一道链表排序题链接在这里 二、解题思路
解题思路使用归并排序用递归实现
第一步先找到链表的中间节点
第二步将链表从中间节点开始断开 找到mid节点(中间节点)的前一个节点将两个链表断开。
第三步重复上述操作再在新链表中找中间节点再分开直到分开到链表剩下一个节点为止。 第四步合并链表。
举个例子 给两个链表一个是1-2-3-4一个链表是0-2-3-5 将这两个有序链表合并成一个有序链表。 申请一个哨兵位的头节点不存储有效数据然后使用l1,l2来遍历两个链表比较l1和l2存储的值的大小。
回到上面的题两个节点之间两两比较只要满足升序要求即可。 合并俩节点后再合并两个链表。
总效果如下图
二.实现的代码 c
typedef struct ListNode ListNode;ListNode*midNode(ListNode*head)
{ListNode*fast head,*slow head;while(fast fast-next){fast fast-next-next;slow slow-next;}return slow;
}//合并链表
ListNode*mergelist(ListNode*head1,ListNode*head2)
{ListNode*newhead (ListNode*)malloc(sizeof(ListNode));ListNode*l1 head1,*l2 head2,*tail newhead;while(l1 l2){if(l1-val l2-val){tail-next l1;l1 l1-next;}else{tail-next l2;l2 l2-next;}tail tail-next;}if(l1!NULL){tail-next l1;}if(l2!NULL){tail-next l2;}ListNode*ret newhead-next;free(newhead);return ret;
}ListNode*tosortList(ListNode*head)
{//空链表和只有一个节点不用再排序了if(headNULL ||head-next NULL){return head;}//找中间节点ListNode*mid midNode(head);//找中间节点的前一个节点ListNode*prev head;while(prev-next!mid){prev prev-next;}//断开链表prev-next NULL;//返回排序后的新链表的头ListNode*left tosortList(head);ListNode*right tosortList(mid);return mergelist(left,right);
}struct ListNode* sortList(struct ListNode* head)
{return tosortList(head);
}总结
使用归并排序是解题的较好的方法。
