148. Sort List
Problem Description
The problem presents us with a singly linked list and requires us to sort it in ascending order. A singly linked list is a data structure where each node contains a value and a reference (or a pointer) to the next node. The head
of the linked list is the first node, and this is the only reference to the linked list that is provided. The challenge is to rearrange the nodes such that their values are in ascending order from the head
to the end of the list. Sorting linked lists is a bit tricky since, unlike arrays, we don't have direct access to the nodes based on index and we cannot use traditional indexing methods.
Intuition
The given solution uses a divide and conquer strategy. Specifically, it uses the merge sort algorithm adapted for linked lists. Here's the intuition behind this approach:
-
Divide phase: First, we split the linked list into two halves. This is done by using a fast and slow pointer approach to find the middle of the linked list. The slow pointer moves one step at a time, while the fast pointer moves two steps. When the fast pointer reaches the end of the list, the slow pointer will be at the middle. We then break the list into two parts from the middle.
-
Conquer phase: We recursively call the
sortList
function on these two halves. Each recursive call will further split the lists into smaller sublists until we are dealing with sublists that either have a single node or are empty. -
Merge phase: After the sublists are sorted, we need to merge them back together. We use a helper pointer to attach nodes in the correct order (the smaller value first). This is similar to the merge operation in the traditional merge sort algorithm on arrays.
-
Base case: The recursion stops when we reach a sublist with either no node or just one node, as a list with a single node is already sorted.
By following these steps, the sortList
function continues to split and merge until the entire list is sorted. The dummy node (dummy
in the code) is used to simplify the merge phase, so we don't have to handle special cases when attaching the first node to the sorted part of the list. At the end, dummy.next
will point to the head of our sorted list, which is what we return.
Learn more about Linked List, Two Pointers, Divide and Conquer, Sorting and Merge Sort patterns.
Solution Approach
The implementation follows the intuition outlined previously and can be broken down as follows:
-
Base Case Handling: The function first checks whether the linked list is empty or contains only a single node by looking for
head is None or head.next is None
. If either condition holds true, it returnshead
as it stands for an already sorted list or no list at all. -
Dividing the List: The list is split into two halves by employing two pointers,
slow
andfast
. These pointers start athead
withfast
one step ahead (pointing tohead.next
). They then loop through the list, withslow
moving one node at a time (slow.next
) andfast
moving two nodes at a time (fast.next.next
). This continues untilfast
reaches the end of the list. At this point,slow
points to the node just before the midpoint of the list.- The split is performed by setting
t
toslow.next
(which is the start of the second half of the list) and then severing the list by settingslow.next
toNone
. This leaves us with two separate lists: one starting fromhead
and ending atslow
, and the other starting fromt
.
- The split is performed by setting
-
Recursive Sorting: The function is recursively called on the two halves of the list,
self.sortList(head)
for the first half andself.sortList(t)
for the second half. The recursive calls continue to split the sublists until they can no longer be split (i.e., the base case). -
Merging: Once the base cases return, the merge phase begins.
-
A dummy node is created with
dummy = ListNode()
, which serves as the starting node of the sorted list. -
A
cur
pointer references it and is used to keep track of the last node in the sorted list as we merge nodes froml1
andl2
. -
In a loop, we compare the values of the nodes at the heads of
l1
andl2
. We attach the smaller node tocur.next
and advance the corresponding pointer (l1
orl2
) as well ascur
. -
This loop continues until either
l1
orl2
is exhausted. Once that happens, the remaining nodes of the non-exhausted list are appended to the end of the merged list because they are already sorted. This is done by the linecur.next = l1 or l2
.
-
-
Returning the Sorted List: The head of the dummy node (
dummy
) does not contain any value and was just a placeholder to ease the merge process. Therefore,dummy.next
refers to the first node of the merged, sorted list, which is the output of the functionsortList
.
In summary, this solution utilizes the merge sort algorithm adapted for linked lists and employs a recursive divide and conquer approach to sorting. It's efficient and effective for sorting linked lists as it doesn't rely on random access memory and works well with the sequential nature of a linked list.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example. Imagine we have a linked list:
14 -> 2 -> 1 -> 3
We want to sort this list in ascending order using the merge sort algorithm designed for linked lists.
-
Base Case Handling: Check if the list is empty or has one node. Our list has multiple nodes, so we move to dividing the list.
-
Dividing the List: We create two pointers,
slow
andfast
. They start off withfast
being one node ahead. As we step through the list,slow
ends up on node 2 andfast
ends up past node 3 (signifying the end of the list).- After the while loop,
slow
is on2
, so we split the list intohead
(pointing at4
) toslow
(pointing at2
) andt
(pointing at1
) to the end.
- After the while loop,
-
Recursive Sorting: We now call
sortList(head)
which sorts the sublist4 -> 2
, andsortList(t)
which sorts the sublist1 -> 3
.In the sublist
4 -> 2
, we would further divide it into4
and2
, and since these are single nodes, they serve as our base cases and are already sorted.Similarly, the sublist
1 -> 3
is divided into1
and3
. Again, these are single nodes and are sorted by definition. -
Merging: We have our sublists sorted:
4
,2
,1
, and3
. We now need to merge them. This is done using the dummy node approach and comparing one by one.- First,
2
and4
are merged into2 -> 4
. - Then
1
and3
are merged into1 -> 3
. - Finally, we merge
2 -> 4
and1 -> 3
into one sorted list. Our pointers would compare2
and1
and choose1
, moving one step. Compare2
and3
and choose2
, and so forth until the list is fully merged into1 -> 2 -> 3 -> 4
.
- First,
-
Returning the Sorted List: The
dummy.next
will point to1
which is the start of our sorted linked list, and that's what we return. Thus, we have successfully sorted the original linked list using the merge sort algorithm:1 -> 2 -> 3 -> 4
.
Solution Implementation
1# Definition for singly-linked list.
2class ListNode:
3 def __init__(self, value=0, next_node=None):
4 self.value = value
5 self.next_node = next_node
6
7class Solution:
8 def sortList(self, head: ListNode) -> ListNode:
9 # Base case: if the list is empty or has only one element it is already sorted.
10 if head is None or head.next_node is None:
11 return head
12
13 # Find the middle of the list to split the list into two halves.
14 slow, fast = head, head.next_node
15 while fast and fast.next_node:
16 slow, fast = slow.next_node, fast.next_node.next_node
17
18 # Split the list into two halves.
19 temp = slow.next_node
20 slow.next_node = None
21 left_half, right_half = self.sortList(head), self.sortList(temp)
22
23 # Merge the two sorted halves.
24 dummy_node = ListNode()
25 current = dummy_node
26 while left_half and right_half:
27 # Compare the current elements of both halves and attach the smaller one to the result.
28 if left_half.value <= right_half.value:
29 current.next_node = left_half
30 left_half = left_half.next_node
31 else:
32 current.next_node = right_half
33 right_half = right_half.next_node
34 current = current.next_node
35
36 # Attach the remaining elements, if any, from either half.
37 current.next_node = left_half or right_half
38
39 # Return the head of the sorted list.
40 return dummy_node.next_node
41
1class Solution {
2
3 /**
4 * Sorts a linked list using the merge sort algorithm.
5 *
6 * @param head The head node of the linked list.
7 * @return The sorted linked list.
8 */
9 public ListNode sortList(ListNode head) {
10 // Base cases: if the list is empty or has just one element, it is already sorted.
11 if (head == null || head.next == null) {
12 return head;
13 }
14
15 // Find the midpoint of the list using the slow and fast pointer approach.
16 ListNode slow = head;
17 ListNode fast = head.next;
18 while (fast != null && fast.next != null) {
19 slow = slow.next; // moves one step at a time
20 fast = fast.next.next; // moves two steps at a time
21 }
22
23 // Split the list into two halves.
24 ListNode mid = slow.next;
25 slow.next = null;
26
27 // Recursively sort each half.
28 ListNode leftHalf = sortList(head);
29 ListNode rightHalf = sortList(mid);
30
31 // Merge the two halves and return the merged sorted list.
32 return merge(leftHalf, rightHalf);
33 }
34
35 /**
36 * Merges two sorted linked lists into one sorted linked list.
37 *
38 * @param left The head node of the first sorted linked list.
39 * @param right The head node of the second sorted linked list.
40 * @return The head node of the merged sorted linked list.
41 */
42 private ListNode merge(ListNode left, ListNode right) {
43 // Create a dummy node to serve as the starting point for the merged list.
44 ListNode dummyHead = new ListNode();
45
46 // Use a pointer to build the new sorted linked list.
47 ListNode current = dummyHead;
48 while (left != null && right != null) {
49 // Choose the node with the smaller value from either left or right,
50 // and append it to the current node of the merged list.
51 if (left.val <= right.val) {
52 current.next = left;
53 left = left.next;
54 } else {
55 current.next = right;
56 right = right.next;
57 }
58 current = current.next;
59 }
60
61 // If any nodes remain in either list, append them to the end of the merged list.
62 current.next = (left == null) ? right : left;
63
64 // Return the head of the merged sorted list, which is the next node of the dummy node.
65 return dummyHead.next;
66 }
67}
68
69/**
70 * Definition for singly-linked list.
71 */
72class ListNode {
73 int val;
74 ListNode next;
75
76 ListNode() {}
77
78 ListNode(int val) {
79 this.val = val;
80 }
81
82 ListNode(int val, ListNode next) {
83 this.val = val;
84 this.next = next;
85 }
86}
87
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode() : val(0), next(nullptr) {}
7 * ListNode(int x) : val(x), next(nullptr) {}
8 * ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13 ListNode* sortList(ListNode* head) {
14 // Base case: if the list is empty or has only one element, it is already sorted.
15 if (!head || !head->next) return head;
16
17 // Use the fast and slow pointer approach to find the middle of the list
18 ListNode* slow = head;
19 ListNode* fast = head->next;
20 while (fast && fast->next) {
21 slow = slow->next;
22 fast = fast->next->next;
23 }
24
25 // Split the list into two halves
26 ListNode* midNext = slow->next;
27 slow->next = nullptr;
28
29 // Recursively sort both halves
30 ListNode* leftHalf = sortList(head);
31 ListNode* rightHalf = sortList(midNext);
32
33 // Merge the two sorted halves
34 ListNode* dummyHead = new ListNode();
35 ListNode* current = dummyHead;
36 while (leftHalf && rightHalf) {
37 // Choose the smaller value from either half
38 if (leftHalf->val <= rightHalf->val) {
39 current->next = leftHalf;
40 leftHalf = leftHalf->next;
41 } else {
42 current->next = rightHalf;
43 rightHalf = rightHalf->next;
44 }
45 // Move to the next node in the merged list
46 current = current->next;
47 }
48
49 // If there are remaining nodes in either half, append them to the merged list
50 current->next = leftHalf ? leftHalf : rightHalf;
51
52 // The merged sorted list is pointed to by the dummy head's next node
53 ListNode* sortedHead = dummyHead->next;
54 delete dummyHead; // Clean up the dummy node
55 return sortedHead;
56 }
57};
58
1// TypeScript definition for a singly-linked list node
2class ListNode {
3 val: number;
4 next: ListNode | null;
5
6 constructor(val?: number, next?: ListNode | null) {
7 this.val = val === undefined ? 0 : val;
8 this.next = next === undefined ? null : next;
9 }
10}
11
12/**
13 * Sorts a singly-linked list using merge sort algorithm.
14 * @param {ListNode | null} head - The head of the singly-linked list to be sorted.
15 * @returns {ListNode | null} - The head of the sorted singly-linked list.
16 */
17function sortList(head: ListNode | null): ListNode | null {
18 // Base case: if the list is empty or has only one node, it's already sorted
19 if (head == null || head.next == null) {
20 return head;
21 }
22
23 // Use fast and slow pointers to find the middle of the linked list
24 let slow: ListNode = head;
25 let fast: ListNode = head.next;
26 while (fast != null && fast.next != null) {
27 slow = slow.next;
28 fast = fast.next.next;
29 }
30
31 // Use recursion to sort both halves of the list
32 let mid: ListNode = slow.next;
33 slow.next = null;
34 let sortedList1: ListNode = sortList(head);
35 let sortedList2: ListNode = sortList(mid);
36
37 // Merge the two sorted halves
38 let dummy: ListNode = new ListNode(); // Temporary dummy node to simplify merge process
39 let current: ListNode = dummy; // Current node for merge process
40
41 // Merge the lists by selecting the smallest of the two nodes at each step
42 while (sortedList1 != null && sortedList2 != null) {
43 if (sortedList1.val <= sortedList2.val) {
44 current.next = sortedList1;
45 sortedList1 = sortedList1.next;
46 } else {
47 current.next = sortedList2;
48 sortedList2 = sortedList2.next;
49 }
50 current = current.next;
51 }
52
53 // Attach remaining nodes (if any) from the non-empty list
54 current.next = sortedList1 == null ? sortedList2 : sortedList1;
55
56 return dummy.next; // The head of the sorted list is next to the dummy node
57}
58
Time and Space Complexity
The given Python code is an implementation of the merge sort algorithm for sorting a linked list. Let's analyze the time complexity and space complexity of the code.
Time Complexity
The merge sort algorithm divides the linked list into halves recursively until each sublist has a single element. Then, it merges these sublists while sorting them. This divide-and-conquer approach leads to a time complexity of O(n log n)
, where n
is the number of nodes in the linked list. This is because:
- The list is split into halves repeatedly, contributing to the
log n
factor (each divide step cuts the linked list size in half). - In each level of the recursion, all
n
elements have to be looked at to merge the sublists, contributing to then
factor.
Therefore, combining both, we get a total time complexity of O(n log n)
.
Space Complexity
The space complexity of the code depends on the implementation of the merge sort algorithm. In this particular version, merge sort is not done in-place; new nodes are not created, but pointers are moved around.
However, due to the use of recursion, there is still a space complexity concern due to the recursive call stack. The maximum depth of the recursion will be O(log n)
, as each level of recursion splits the list in half. Hence, the space complexity is O(log n)
, which is derived from the depth of the recursion stack.
In summary:
- Time Complexity:
O(n log n)
- Space Complexity:
O(log n)
Learn more about how to find time and space complexity quickly using problem constraints.
You are given an array of intervals where intervals[i] = [start_i, end_i]
represent the start and end of the ith
interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.