148. Sort List

MediumLinked ListTwo PointersDivide and ConquerSortingMerge Sort

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 returns head 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 and fast. These pointers start at head with fast one step ahead (pointing to head.next). They then loop through the list, with slow moving one node at a time (slow.next) and fast moving two nodes at a time (fast.next.next). This continues until fast 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 to slow.next (which is the start of the second half of the list) and then severing the list by setting slow.next to None. This leaves us with two separate lists: one starting from head and ending at slow, and the other starting from t.
Recursive Sorting: The function is recursively called on the two halves of the list, self.sortList(head) for the first half and self.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 from l1 and l2.
- In a loop, we compare the values of the nodes at the heads of l1 and l2. We attach the smaller node to cur.next and advance the corresponding pointer (l1 or l2) as well as cur.
- This loop continues until either l1 or l2 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 line cur.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 function sortList.

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 Evaluator

Example Walkthrough

Let's illustrate the solution approach using a small example. Imagine we have a linked list:

4 -> 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 and fast. They start off with fast being one node ahead. As we step through the list, slow ends up on node 2 and fast ends up past node 3 (signifying the end of the list).
- After the while loop, slow is on 2, so we split the list into head (pointing at 4) to slow (pointing at 2) and t (pointing at 1) to the end.
Recursive Sorting: We now call sortList(head) which sorts the sublist 4 -> 2, and sortList(t) which sorts the sublist 1 -> 3.

In the sublist 4 -> 2, we would further divide it into 4 and 2, and since these are single nodes, they serve as our base cases and are already sorted.

Similarly, the sublist 1 -> 3 is divided into 1 and 3. Again, these are single nodes and are sorted by definition.
Merging: We have our sublists sorted: 4, 2, 1, and 3. We now need to merge them. This is done using the dummy node approach and comparing one by one.
- First, 2 and 4 are merged into 2 -> 4.
- Then 1 and 3 are merged into 1 -> 3.
- Finally, we merge 2 -> 4 and 1 -> 3 into one sorted list. Our pointers would compare 2 and 1 and choose 1, moving one step. Compare 2 and 3 and choose 2, and so forth until the list is fully merged into 1 -> 2 -> 3 -> 4.
Returning the Sorted List: The dummy.next will point to 1 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 the n 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: