Sort a linked list in O(n log n) time using constant space complexity.
Merge Sort.
/**
* Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class SortList {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode[] splits = split(head);
ListNode left = sortList(splits[0]);
ListNode right = sortList(splits[1]);
return merge(left, right);
}
private ListNode[] split(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
if (fast == null) {
break;
}
slow = slow.next;
}
fast = slow.next;
slow.next = null;
return new ListNode[]{ head, fast};
}
private ListNode merge(ListNode head1, ListNode head2) {
ListNode head = new ListNode(0);
ListNode tmp = head;
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
tmp.next = head1;
head1 = head1.next;
} else {
tmp.next = head2;
head2 = head2.next;
}
tmp = tmp.next;
}
if (head1 != null) {
tmp.next = head1;
} else {
tmp.next = head2;
}
return head.next;
}
}