DAY 73 - 86. Partition List

Hey Guys! Today we are on the 73rd day and we are going to solve today's daily leetcode problem. Let's start with breaking down the problem and then get to into the algorithm.

Question: 86. Partition List

Given the head of a linked list and a value x, partition it 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 1:

• 
• Input: head = [1,4,3,2,5,2], x = 3
• Output: [1,2,2,4,3,5]

Question Breakdown and Intuition:

• To put it out simply, we hae been given a value x.
• There are elements present in the linked list, which are either greater&equal to or lesser than the value x.
• We also have to maintain a relative order of the elements in each of the partition.
• Let's not think much and put all of our elements lesser than value in one node and greater ones in another node.
• Let's combine them then according to the combinations, give out our result.

Algorithm Approach:

• Initialize 5 pointers : Head Of Smaller and Head of Greater & Next of Smaller and Greater & One pointer temp to traverse the linked list.
• While Traversing the linked list, we check if it's value is less than the given val x. If the head of our smaller is null, this tells us that there has been no such value up until this that has been smaller than given val x.
• So we initialize both the next and head pointers to current temp otherwise we give it's next iterator's value to temp and move it ahead.
• We follow the same thing for greater than equal to x.
• We do some check ups , if(our smallerHead is nullptr) which means there exists no value greater than equal to x, we can simply return the formed greaterHead or head because they will be same else we attach both the lists together.
• We also assign the last value of greaterHead to null to make it a complete linked list.
• We return smallerHead as it's our completed linked list.

Code:

/**
 * 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* partition(ListNode* head, int x) {
        ListNode* greaterHead = NULL;
        ListNode* smallerHead = NULL;
        ListNode* greaterNext = NULL;
        ListNode* smallerNext = NULL;
        if(head == NULL) return NULL;

        ListNode* temp = head;

        while(temp!= nullptr){
            if(temp->val < x){
                if(smallerHead == NULL){
                    smallerHead = temp;
                    smallerNext = temp;
                }
                else{
                    smallerNext->next = temp;
                    smallerNext = temp;
                }
            }
            else{
                if(greaterHead == NULL){
                    greaterHead = temp;
                    greaterNext = temp;
                }
                else{
                    greaterNext->next = temp;
                    greaterNext = temp;
                }
            }
            temp = temp->next;
        }
        if (smallerHead == nullptr)
            return greaterHead;
        else {
            smallerNext->next = greaterHead;
        }

        if (greaterNext != nullptr)
            greaterNext->next = nullptr;

        return smallerHead;
    }
};

Complexity Analysis: