148. Sort List

Problem Statement

Given the head of a linked list, sort the list in ascending order and return the sorted list.

Approach

For this problem, we can implement a merge sort algorithm with O(1) space complexity by using a bottom-up approach. The key steps involve:

1. Determining the length of the linked list
2. Splitting the list into sublists of increasing sizes
3. Merging these sublists in pairs until we have a fully sorted list

Solution Code

class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        
        // Calculate list length
        int length = 0;
        ListNode* node = head;
        while (node) {
            length++;
            node = node->next;
        }
        
        ListNode dummy(0);
        dummy.next = head;
        
        // Bottom-up merge sort
        for (int size = 1; size < length; size *= 2) {
            ListNode* curr = dummy.next;
            ListNode* tail = &dummy;
            
            while (curr) {
                ListNode* left = curr;
                ListNode* right = split(left, size);
                curr = split(right, size);
                
                tail = merge(left, right, tail);
            }
        }
        
        return dummy.next;
    }
    
private:
    // Split list into two parts and return the head of the second part
    ListNode* split(ListNode* head, int size) {
        if (!head) return nullptr;
        
        for (int i = 1; head->next && i < size; i++) {
            head = head->next;
        }
        
        ListNode* second = head->next;
        head->next = nullptr;
        return second;
    }
    
    // Merge two sorted lists and attach to tail
    ListNode* merge(ListNode* l1, ListNode* l2, ListNode* tail) {
        while (l1 && l2) {
            if (l1->val > l2->val) {
                tail->next = l2;
                l2 = l2->next;
            } else {
                tail->next = l1;
                l1 = l1->next;
            }
            tail = tail->next;
        }
        
        if (l1) tail->next = l1;
        if (l2) tail->next = l2;
        
        while (tail->next) tail = tail->next;
        return tail;
    }
};

56. Merge Intervals

Problem Statement

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of non-overlapping intervals that cover all intervals in the input.

Approach

The solution involves sorting the intervals based on their start values, then iterating through them while merging overlapping intervals. The algorithm works as follows:

1. Sort intervals based on their start values
2. Initialize a result list with the first interval
3. For each subsequent interval, if it overlaps with the last interval in the result, merge them
4. Otherwise, add it as a new interval to the result

Solution Code

class Solution {
public:
    vector<vector>> merge(vector<vector>>& intervals) {
        // Sort intervals based on start values
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        });
        
        vector<vector>> merged;
        
        for (const auto& interval : intervals) {
            // If the list of merged intervals is empty or if the current
            // interval does not overlap with the previous, append it
            if (merged.empty() || merged.back()[1] < interval[0]) {
                merged.push_back(interval);
            } else {
                // Otherwise, there is an overlap, so we merge the current and previous intervals
                merged.back()[1] = max(merged.back()[1], interval[1]);
            }
        }
        
        return merged;
    }
};
</vector></int></int></vector></vector>

Key Takeaways

• For linked list problems, remember that pointers represent memory addresses and operations on them affect the underlying nodes
• When sorting linked lists, consider space complexity constraints - bottom-up merge sort can achieve O(1) space
• For interval problems, sorting is often the first step to sipmlify the merging process
• Always handle edge cases (empty inputs, single elements) in your implementations