Sort a Linked List in O(NLogN)
Loved this question! https://leetcode.com/problems/sort-list/description/
If you want to guarantee O(NLogN), you'll need to select a different method. One that is guaranteed O(NLogN) for all the cases is MergeSort, although it comes with a stack overhead hence not preferred in real applications. But that's what I'm going to use here: MergeSort.
The approach for MergeSort in a nutshell is the following:
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->5It requires a little fundamentals of Sorting: if you use QuickSort, which is the best sorting algorithm on average, you won't be able to guarantee O(NLogN) for all the cases since in the worst case scenario QuickSort performs in O(N^2)-time.
If you want to guarantee O(NLogN), you'll need to select a different method. One that is guaranteed O(NLogN) for all the cases is MergeSort, although it comes with a stack overhead hence not preferred in real applications. But that's what I'm going to use here: MergeSort.
The approach for MergeSort in a nutshell is the following:
- Handle the base cases when the list has zero, one or two elements
- Split the list into 2. You will use the "slow pointer, fast pointer" approach to find the mid-point of the list
- Call recursively for the 2 lists from the previous step
- Now merge the 2 lists in linear time (they are sorted already!)
That's it, worked well, cheers, ACC.
public class Solution
{
public ListNode SortList(ListNode head)
{
if (head == null) return null;
if (head.next == null) return head;
if (head.next.next == null)
{
if (head.val > head.next.val)
{
int temp = head.val;
head.val = head.next.val;
head.next.val = temp;
}
return head;
}
//Find the 1/2
ListNode back = head;
ListNode front = head.next;
while (front != null && front.next != null)
{
back = back.next;
front = front.next;
front = front.next;
}
front = back.next;
back.next = null;
back = head;
return MergeLists(SortList(back), SortList(front));
}
private ListNode MergeLists(ListNode l1, ListNode l2)
{
ListNode retVal = null;
ListNode current = null;
ListNode i1 = l1;
ListNode i2 = l2;
while (i1 != null && i2 != null)
{
if (i1.val < i2.val)
{
if (retVal == null)
{
retVal = new ListNode(i1.val);
current = retVal;
}
else
{
current.next = new ListNode(i1.val);
current = current.next;
}
i1 = i1.next;
}
else if (i1.val > i2.val)
{
if (retVal == null)
{
retVal = new ListNode(i2.val);
current = retVal;
}
else
{
current.next = new ListNode(i2.val);
current = current.next;
}
i2 = i2.next;
}
else
{
//2x
for (int i = 0; i < 2; i++)
{
if (retVal == null)
{
retVal = new ListNode(i1.val);
current = retVal;
}
else
{
current.next = new ListNode(i1.val);
current = current.next;
}
}
i1 = i1.next;
i2 = i2.next;
}
}
while (i1 != null)
{
if (retVal == null)
{
retVal = new ListNode(i1.val);
current = retVal;
}
else
{
current.next = new ListNode(i1.val);
current = current.next;
}
i1 = i1.next;
}
while (i2 != null)
{
if (retVal == null)
{
retVal = new ListNode(i2.val);
current = retVal;
}
else
{
current.next = new ListNode(i2.val);
current = current.next;
}
i2 = i2.next;
}
return retVal;
}
}
Comments
I also ended up using merge sort, but this technically violates one of the problem requirements of using constant space - merge sort uses recursion and as such stack, which non-constant space :)
Reply Deleteclass Solution:
def merge(self, head1, head2):
merged = ListNode(-1)
prev = merged
while head1 and head2:
if head1.val <= head2.val:
temp = head1.next
prev.next = head1
prev, head1 = head1, temp
else:
temp = head2.next
prev.next = head2
prev, head2 = head2, temp
if head1:
prev.next = head1
if head2:
prev.next = head2
return merged.next
def split(self, head):
slow, fast = head, head
while fast and fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
head2, slow.next = slow.next, None
return head, head2
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
head1, head2 = self.split(head)
head1, head2 = self.sortList(head1), self.sortList(head2)
return self.merge(head1, head2)
https://gist.github.com/ttsugriy/00a8141fb3540d6cea36cb34933ba83d
Post a Comment
[γγ¬γΌγ ]