Given the head of a linked list, return the list after sorting it in ascending order.
Example 1:
Input: head = [4,2,1,3] Output: [1,2,3,4]
Example 2:
Input: head = [-1,5,3,4,0] Output: [-1,0,3,4,5]
Example 3:
Input: head = [] Output: []
Constraints:
[0, 5 * 104].-105 <= Node.val <= 105
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
return partition(head);
}
private ListNode findMiddle(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode partition(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode mid = findMiddle(head), lt = head, rt = mid.next;
mid.next = null;
lt = partition(lt);
rt = partition(rt);
return merge(lt, rt);
}
private ListNode merge(ListNode lt, ListNode rt) {
ListNode dummy = new ListNode(0), curr = dummy;
while (lt != null && rt != null) {
if (lt.val <= rt.val) {
curr.next = lt;
lt = lt.next;
} else {
curr.next = rt;
rt = rt.next;
}
curr = curr.next;
}
if (lt != null)
curr.next = lt;
else if (rt != null)
curr.next = rt;
return dummy.next;
}
}