We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Given the head of a linked list, return the list after sorting it in ascending order.
head
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
O(n logn)
O(1)
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: []
[0, 5 * 104]
-105 <= Node.val <= 105
The text was updated successfully, but these errors were encountered:
/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */ function sortList(head: ListNode | null): ListNode | null { if (head === null || head.next === null) { return head; } let guard: ListNode | null = new ListNode(-1, head); let slow: ListNode | null = guard; let fast: ListNode | null = guard; while(fast !== null && fast.next !== null) { fast = fast.next.next; slow = slow!.next; } const rightList = slow!.next; slow!.next = null; const leftList = guard.next; let leftSorted = sortList(leftList); let rightSorted = sortList(rightList); guard.next = null; let patrol = guard; while (leftSorted !== null && rightSorted !== null) { if (leftSorted.val <= rightSorted.val) { patrol.next = leftSorted; leftSorted = leftSorted.next; } else { patrol.next = rightSorted; rightSorted = rightSorted.next; } patrol = patrol.next; patrol.next = null; } patrol.next = leftSorted || rightSorted; return guard.next; };
Sorry, something went wrong.
No branches or pull requests
148. Sort List
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 andO(1)
memory (i.e. constant space)?Example 1
Example 2
Example 3
Constraints
[0, 5 * 104]
.-105 <= Node.val <= 105
The text was updated successfully, but these errors were encountered: