Software Tech

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.

DAY 73 – 86. Partition List

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

: 86. Partition List

Given the head of linked and a x, partition it such that all nodes less than x come before nodes greater than or equal to x.

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 :

To put it out simply, we hae been given a value x.
There are elements present in the , 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 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 & of Smaller and Greater & One pointer temp to traverse the linked .
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 and head pointers to current temp otherwise we give it's next iterator's value to temp and 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 {
* 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:

Algorithm
Time Complexity
Space Complexity

Two Pointer Approach
O(n)
O(n)

About Author

Nayan Pahuja

Leave a Reply

SOFAIO BLOG We would like to show you notifications for the latest news and updates.
Dismiss
Allow Notifications