algoadvance

Leetcode 86. Partition List

Problem Statement

You are given the head of a linked list and a value x. You need to partition the linked list such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

Clarifying Questions

1. Q: What should we do if the list is empty? A: Return the empty list.

2. Q: What if all nodes have values less than x? A: Return the list as it is.

3. Q: Can x be negative? A: Yes, x can be any integer.

4. Q: Do we need to handle memory management for the nodes? A: No, just rearrange the nodes without creating new ones, unless necessary during traversal (like dummy nodes).

Strategy

1. Initialize Two New Lists:
   • Create two dummy nodes: one for nodes less than x (less_dummy) and one for nodes greater than or equal to x (greater_dummy).
2. Traverse the Given List:
   • Iterate through the list, appending nodes to the end of the “less than” list or the “greater than or equal to” list based on their values.
3. Combine Lists:
   • After partitioning all nodes into the two lists, combine them by pointing the last node of the “less than” list to the beginning of the “greater than or equal to” list.
4. Return Result:
   • Return the combination of the two lists starting from the node next to less_dummy.

Code

Here is a C++ implementation of the solution:

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

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        // Dummy nodes
        ListNode less_dummy(0), greater_dummy(0);
        
        // Pointers to the current nodes in the "less than" and "greater than or equal to" lists
        ListNode *less = &less_dummy, *greater = &greater_dummy;

        // Traverse the given list
        while (head != nullptr) {
            if (head->val < x) {
                less->next = head;
                less = less->next;
            } else {
                greater->next = head;
                greater = greater->next;
            }
            head = head->next;
        }

        // Ensure the end of the "greater" list points to nullptr
        greater->next = nullptr;

        // Combine the two lists
        less->next = greater_dummy.next;

        return less_dummy.next;
    }
};

Time Complexity

• Traversal Time: (O(n)) where (n) is the number of nodes in the list. We traverse the list a single time.

• Space Complexity: (O(1)) extra space, not considering the space used for the output list and the input list.

This solution effectively segregates the nodes in one pass and combines the partitions in constant time.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?