algoadvance

Leetcode 148. Sort List

Problem Statement:

Given the head of a linked list, return the list after sorting it in ascending order.

Example:

Constraints:

Clarifying Questions:

  1. What is the structure of the linked list?
    • The linked list is a singly linked list where each node has an integer value and a pointer to the next node.
  2. Can the linked list be empty?
    • Yes, the linked list can be empty.
  3. Is there a constraint on the additional space we can use?
    • The problem does not explicitly mention space complexity constraints, but sorting in O(1) auxiliary space is preferred.

Strategy:

To solve the problem efficiently, we can use a sorting algorithm suitable for linked lists, such as Merge Sort, which has O(n log n) time complexity.

Steps:

  1. Find the Middle: Use the slow and fast pointer strategy to find the middle of the linked list.
  2. Divide: Split the linked list into two halves.
  3. Sort Each Half: Recursively sort each half.
  4. Merge: Merge the two sorted halves.

Code:

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }

        // Step 1: Find the middle point of the list
        ListNode* mid = findMiddle(head);

        // Step 2: Split the list into two halves
        ListNode* right = mid->next;
        mid->next = NULL;  // Split the list into two halves

        // Step 3: Sort each half
        ListNode* left = sortList(head);
        right = sortList(right);

        // Step 4: Merge the sorted halves
        return mergeTwoLists(left, right);
    }

private:
    ListNode* findMiddle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head->next;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        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;
        }

        if (l1) {
            tail->next = l1;
        } else {
            tail->next = l2;
        }

        return dummy.next;
    }
};

Time Complexity:

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI