【LeetCode】 sort list 单链表的归并排序
题目:Sort a linked list in O(n log n) time using constant space complexity.
思路:要求时间复杂度O(nlogn)
知识点:归并排序,链表找到中点的方法
存在的缺点:边界条件多考虑!!!
/** * LeetCode Sort List Sort a linked list in O(n log n) time using constant space complexity. * 题目:将一个单链表进行排序,时间复杂度要求为o(nlogn) * 思路:1时间复杂度为o(nlog n)的排序算法有:归并排序、快排(期望)、堆排序 * 2、单链表排序用归并排序,双链表排序用快排 * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ package javaTrain; class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } public class Train4 { public ListNode sortList(ListNode head) { if(head == null || head.next == null) return head; ListNode fast = head; ListNode slow = head; while(fast.next.next != null && slow.next != null){ fast = fast.next.next; //使得当遍历完该链表之后一个指向中间一个指向末尾,即找到链表中点 slow = slow.next; } ListNode list2 = slow.next; slow.next = null; head = sortList(head); list2 = sortList(list2); return merge(head,list2); } private static ListNode merge(ListNode list1,ListNode list2){ if(list1 == null) return list2; if(list2 == null) return list1; ListNode head = new ListNode(0); ListNode last = head; while(list1.next != null && list2.next != null){ if(list1.val <= list2.val){ last.next = list1; list1 = list1.next; } else{ last.next = list2; list2 = list2.next; } last = last.next; } if(list1 != null) last.next = list1; else if(list2 != null) last.next = list2; return head.next; } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。