腾讯五十题 No.33 排序链表
2022/2/9 6:13:40
本文主要是介绍腾讯五十题 No.33 排序链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
递归排序三部曲:①快慢指针找中点;②递归调用mergeSort; ③合并两个链表
归并
class Solution { public ListNode sortList(ListNode head){ return mergeSort(head); } //归并排序 private ListNode mergeSort(ListNode head){ //如果没有节点、只有一个节点,无需排序 if(head == null || head.next == null) return head; //快慢指针找中位点 ListNode slow = head,fast = head.next.next,l,r; while(fast!=null && fast.next!=null){ slow = slow.next; fast = fast.next.next; } //对右半部分进行归并排序 r = mergeSort(slow.next); //判断链表是否结束 slow.next = null; //对左半部分进行归并排序 l = mergeSort(head); return mergeList(l,r); } //合并链表 private ListNode mergeList(ListNode l,ListNode r){ //临时头节点 ListNode tmpHead = new ListNode(-1); ListNode p = tmpHead; while(l!=null && r!=null){ if(l.val <r.val){ p.next = l; l = l.next; }else{ p.next = r; r = r.next; } p = p.next; } p.next = l == null?r:l; return tmpHead.next; } }
快排(大佬说头条面到了)
class Solution { public ListNode sortList(ListNode head) { if(head==null||head.next==null) return head; // 没有条件,创造条件。自己添加头节点,最后返回时去掉即可。 ListNode newHead=new ListNode(-1); newHead.next=head; return quickSort(newHead,null); } // 带头结点的链表快速排序 private ListNode quickSort(ListNode head,ListNode end){ if (head==end||head.next==end||head.next.next==end) return head; // 将小于划分点的值存储在临时链表中 ListNode tmpHead=new ListNode(-1); // partition为划分点,p为链表指针,tp为临时链表指针 ListNode partition=head.next,p=partition,tp=tmpHead; // 将小于划分点的结点放到临时链表中 while (p.next!=end){ if (p.next.val<partition.val){ tp.next=p.next; tp=tp.next; p.next=p.next.next; }else { p=p.next; } } // 合并临时链表和原链表,将原链表接到临时链表后面即可 tp.next=head.next; // 将临时链表插回原链表,注意是插回!(不做这一步在对右半部分处理时就断链了) head.next=tmpHead.next; quickSort(head,partition); quickSort(partition,end); // 题目要求不带头节点,返回结果时去除 return head.next; } }
这篇关于腾讯五十题 No.33 排序链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-08如何在敏捷项目中实现高效测试?
- 2024-07-08用户故事一定要有 “So that...” 吗?
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt