给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
进阶:
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution { private ListNode findMid(ListNode head) { if (head == null || head.next == null || head.next.next == null) { return head; } ListNode slow = head.next; ListNode fast = head.next.next; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } private ListNode merge(ListNode p1, ListNode p2) { ListNode newHead = new ListNode(), tail = newHead; while (p1 != null && p2 != null) { if (p1.val <= p2.val) { tail.next = p1; p1 = p1.next; } else { tail.next = p2; p2 = p2.next; } tail = tail.next; } if (p1 != null) { tail.next = p1; } if (p2 != null) { tail.next = p2; } return newHead.next; } private ListNode mergeSort(ListNode head) { if (head == null || head.next == null) { return head; } ListNode mid = findMid(head); ListNode next = mid.next; mid.next = null; ListNode p1 = mergeSort(head), p2 = mergeSort(next); return merge(p1, p2); } public ListNode sortList(ListNode head) { if (head == null) { return head; } return mergeSort(head); } public static void main(String[] args) { ListNode n1 = new ListNode(4); ListNode n2 = new ListNode(2); ListNode n3 = new ListNode(1); ListNode n4 = new ListNode(3); n1.next = n2; n2.next = n3; n3.next = n4; ListNode node = new Solution().sortList(n1); while (node != null) { System.out.println(node.val); node = node.next; } } } class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } }