Chapter 2 - Problem 4 - Partition

Problem

Write code to partition a linked list around a value x, such that all nodes less than x come
before all nodes greater than or equal to x. If x is contained within the list, the values of x only need to be after the elements less than x (see below). The partition element x can appear anywhere in the "right partition"; it does not need to appear between the left and right partitions.

EXAMPLE
Input : 3 -> 1 -> 4 -> 2 (partition = 3)
Output : 1 -> 2 -> 3 -> 4 (one example of output)

Solution

Solution in C++

Graphic explanation:

template<typename T>
class Node {
    public:
        T data;
        Node* next;
        
        Node() = default;
        Node(const T& value) : data(value), next(NULL) {}
};

template<typename T>
class LinkedList {
    protected:
        Node<T>* head;
};

template<typename T>
class Solution : public LinkedList<T> {
    public:
        void partition(int n) {
            Node<T> *beforeXStart = NULL;
            Node<T> *beforeXEnd = NULL;
            Node<T> *afterXStart = NULL;
            Node<T> *afterXEnd = NULL;
            Node<T> *current = this->head;
            
            /*
                We keep two lists, one for elements < n and one for elements > n.
                In the end, we merge them. 
            */
            while(current != NULL) {
                if(current->data < n) {
                    if(beforeXStart == NULL) {
                        beforeXStart = beforeXEnd = current;
                    }
                    else {
                        beforeXEnd->next = current;
                        beforeXEnd = beforeXEnd->next;
                    }
                }
                else {
                    if(afterXStart == NULL) {
                        afterXStart = afterXEnd = current;
                    }
                    else {
                        afterXEnd->next = current;
                        afterXEnd = afterXEnd->next;
                    }
                }
                current = current->next;
            }
            /* Because there could be other elements < n */
            afterXEnd->next = NULL;
            /* We merge the two pieces */
            beforeXEnd->next = afterXStart;
            this->head = beforeXStart;
        }
};

• Time complexity: $O(N)$ (where N is the size of the list)
• Space complexity: $O(1)$

Shorter solution in C++

Graphic explanation:

Node() = default;
Node(const T& value) : data(value), next(NULL) {}
};

if (current->data < n) {
current->next = this->head;
this->head = current;
}
else {
tail->next = current;
tail = tail->next;
}
current = next;
}
/* Because there could be other elements < n */
tail->next = NULL;
}
};

- **Time complexity:** $O(N)$ (where _N_ is the size of the list)
- **Space complexity:** $O(1)$