0148. Sort List
Medium | Linked List + MergeSort | 172 ms (98.38%), 45.6 MB (95.85%)
Source: LeetCode - Sort List GitHub: Solution / Performance
Given the head of a linked list, return the list after sorting it in ascending order.
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
Constraints:
The number of nodes in the list is in the range
[0, 5 * 10^4].-10^5 <= Node.val <= 10^5
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Input: head = []
Output: []Before splitting, we need to get the length of the input linked list.
Then split the linked list bottom-up by starting with size = 1, this size will grow two times of itself in each iteration by size *= 2 until size >= length.
For the process of splitting and merging, we need to maintain two pointers:
splitHead is to check whether the splitting process needs to end or not.
mergeHead is for merging two split linked lists so that we can maintain relative order for the next splitting process.
class Solution:
def sortList(self, head: ListNode) -> ListNode:
# (base case)
if not head or not head.next: return head
# ==================================================
# Linked List + Merge Sort (Iterative) =
# ==================================================
# time : O(nlog(n))
# space : O(1)
length = self.getSize(head)
ret, size = ListNode(0, head), 1
while size < length:
splitHead, mergeHead = ret.next, ret
while splitHead:
left = splitHead
right = self.split(size, left)
splitHead = self.split(size, right)
mergeHead = self.merge(left, right, mergeHead)
size *= 2
return ret.next
def getSize(self, node: ListNode) -> int:
size, tmp = 0, node
while tmp: size, tmp = size + 1, tmp.next
return size
def split(self, size: int, node: ListNode) -> ListNode:
pre = None
for i in range(size):
if not node: break
pre, node = node, node.next
# (break the link)
if pre: pre.next = None
return node
def merge(self, left: ListNode, right: ListNode, head: ListNode) -> ListNode:
while left and right:
if left.val <= right.val: head.next, left = left, left.next
else: head.next, right = right, right.next
head = head.next
head.next = left if left else right
while head.next: head = head.next
return headclass Solution {
/**
* @time : O(nlog(n))
* @space : O(1)
*/
public ListNode sortList(ListNode head) {
/* base case */
if(head == null || head.next == null) return head;
int len = getLen(head);
int size = 1;
ListNode ret = new ListNode(0, head);
while(size < len) {
ListNode splitHead = ret.next, mergeHead = ret;
while(splitHead != null) {
ListNode left = splitHead;
ListNode right = split(size, left);
splitHead = split(size, right);
mergeHead = merge(left, right, mergeHead);
}
size *= 2;
}
return ret.next;
}
public int getLen(ListNode head) {
int len = 0;
ListNode cur = head;
while(cur != null) {
len++;
cur = cur.next;
}
return len;
}
public ListNode split(int size, ListNode node) {
ListNode pre = null;
for(int i=0 ; i<size ; i++) {
if(node == null) break;
pre = node;
node = node.next;
}
/* break the link */
if(pre != null) pre.next = null;
return node;
}
public ListNode merge(ListNode left, ListNode right, ListNode head) {
while(left != null && right != null) {
if(left.val <= right.val) {
head.next = left;
left = left.next;
} else {
head.next = right;
right = right.next;
}
head = head.next;
}
head.next = (left != null) ? left : right;
while(head.next != null) head = head.next;
return head;
}
}Last updated
Was this helpful?