148. Sort List (Medium)
https://leetcode.com/problems/sort-list/
Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3 Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0 Output: -1->0->3->4->5
Solutions
class Solution {
// Employ merge sort algorithm to solve this problem, be careful for the corn cases,
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
int len = 0;
ListNode p = head;
while (p != null) {
len++;
p = p.next;
}
// Find the middle position to split the list into two sub list
int mid = 0;
ListNode left = head;
ListNode right = head.next;
// Think it over if the len is odd or even
while (mid < (len / 2 - 1)) {
left = left.next;
right = right.next;
mid++;
}
// You must split it. This situation is totally different from those of using
// array to hold elements.
left.next = null;
left = sortList(head);
right = sortList(right);
//merge
// dummy head, easy for insertion
ListNode dummy = new ListNode(-1);
ListNode pointer = dummy;
while (left != null && right != null) {
if (left.val <= right.val) {
pointer.next = left;
left = left.next;
pointer = pointer.next;
} else {
pointer.next = right;
right = right.next;
pointer = pointer.next;
}
}
while (left != null) {
pointer.next = left;
pointer = pointer.next;
left = left.next;
}
while (right != null) {
pointer.next = right;
pointer = pointer.next;
right = right.next;
}
return dummy.next;
}
}