Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

148. Sort List - Leetcode Solution

Code Implementation

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        # Split the list into two halves
        prev, slow, fast = None, head, head
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        prev.next = None  # Cut the list
        
        # Sort each half
        l1 = self.sortList(head)
        l2 = self.sortList(slow)
        
        # Merge sorted halves
        return self.merge(l1, l2)
    
    def merge(self, l1, l2):
        dummy = ListNode()
        tail = dummy
        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        tail.next = l1 or l2
        return dummy.next
      
// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        
        // Split the list into halves
        ListNode* prev = nullptr;
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        prev->next = nullptr; // Cut
        
        ListNode* l1 = sortList(head);
        ListNode* l2 = sortList(slow);
        
        return merge(l1, l2);
    }
    
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummy;
        ListNode* tail = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
};
      
// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        
        // Split list into halves
        ListNode prev = null, slow = head, fast = head;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null; // Cut
        
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);
        
        return merge(l1, l2);
    }
    
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}
      
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    if (!head || !head.next) return head;
    
    // Split list into halves
    let prev = null, slow = head, fast = head;
    while (fast && fast.next) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    prev.next = null; // Cut
    
    let l1 = sortList(head);
    let l2 = sortList(slow);
    
    return merge(l1, l2);
};

function merge(l1, l2) {
    let dummy = new ListNode(0);
    let tail = dummy;
    while (l1 && l2) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = l1 ? l1 : l2;
    return dummy.next;
}

Problem Description

Given the head of a singly linked list head, sort the list in ascending order and return its head. You must perform the sort in-place without allocating extra space for another list (i.e., O(1) auxiliary space).

  • Each node contains an integer value.
  • You cannot change the values inside the nodes, only the node connections (pointers) themselves.
  • There is only one valid sorted list for any given input.
  • The input list may be empty or contain only one node.

Thought Process

The first idea that comes to mind might be to extract all the values from the linked list, sort them using a standard sorting algorithm (like quicksort or mergesort), and then rebuild the list. However, this approach would require O(n) extra space, which is not allowed.

Instead, we need to sort the list by rearranging the existing nodes. Since random access is not available in linked lists, algorithms like quicksort are not efficient. Mergesort, on the other hand, is well-suited for linked lists because it only requires sequential access and can be implemented in-place by manipulating pointers.

Therefore, we shift from a brute-force or array-based mindset to a pointer-based, divide-and-conquer strategy using mergesort.

Solution Approach

We use the merge sort algorithm tailored for linked lists. The key steps are:

  1. Base Case: If the list is empty or has only one node, it's already sorted.
  2. Splitting the List: Use the slow and fast pointer technique to find the middle of the list. The slow pointer moves one step at a time, while the fast pointer moves two steps. When the fast pointer reaches the end, the slow pointer will be at the midpoint. We then cut the list into two halves.
  3. Recursive Sort: Recursively sort both halves of the list.
  4. Merge: Merge the two sorted halves by comparing their node values and rearranging pointers.

We use a dummy node to simplify the merging process, avoiding special cases for the head node.

Example Walkthrough

Let's consider the input list: 4 -> 2 -> 1 -> 3.

  1. First Split: The list is split into 4 -> 2 and 1 -> 3.
  2. Sort Left Half: 4 -> 2 is split into 4 and 2. Both are single nodes, so already sorted.
  3. Merge Left Half: Merge 4 and 2 to get 2 -> 4.
  4. Sort Right Half: 1 -> 3 is split into 1 and 3. Both are single nodes.
  5. Merge Right Half: Merge 1 and 3 to get 1 -> 3.
  6. Final Merge: Merge 2 -> 4 and 1 -> 3:
    • Compare 2 and 1: 1 is smaller.
    • Compare 2 and 3: 2 is smaller.
    • Compare 4 and 3: 3 is smaller.
    • Only 4 remains.

    Result: 1 -> 2 -> 3 -> 4

Time and Space Complexity

  • Brute-force approach: Extracting values and sorting them takes O(n log n) time and O(n) space for the array.
  • Optimized (Mergesort) approach:
    • Time Complexity: O(n log n), because the list is split in half each time and merging takes O(n) at each level.
    • Space Complexity: O(1) auxiliary space, as we only use pointers and no extra data structures. However, the recursion stack uses O(log n) space.

Summary

To sort a linked list efficiently in-place, we use the mergesort algorithm, which is naturally suited for linked lists due to its sequential access pattern and pointer manipulation. By recursively splitting the list and merging sorted halves, we achieve O(n log n) time complexity and O(1) auxiliary space, making the solution both efficient and elegant.