148. Sort List
Explanation
To sort a linked list in O(n logn) time and O(1) space, we can use the merge sort algorithm. The idea is to divide the list into two halves, sort each half recursively, and then merge the sorted halves back together. This approach guarantees the desired time complexity and uses only a constant amount of extra space.
- Splitting: Find the middle of the linked list using the slow and fast pointer technique.
- Recursively sort: Sort the two halves of the list recursively.
- Merge: Merge the two sorted halves back together.
Time complexity: O(n logn)
Space complexity: O(1)
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode mid = findMiddle(head);
ListNode right = mid.next;
mid.next = null; // break the list
ListNode leftSorted = sortList(head);
ListNode rightSorted = sortList(right);
return merge(leftSorted, rightSorted);
}
private ListNode findMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
if (l1 != null) {
current.next = l1;
} else {
current.next = l2;
}
return dummy.next;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.