86. Partition List

Problem Statement

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]

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

Constraints:

The number of nodes in the list is in the range [0, 200].
-100 <= Node.val <= 100
-200 <= x <= 200

Intuition

Approach:

Maintain large_start, large_end, Similarly for small start and end

These are going to track the larger than x chain start and end points
And similarly for start pointers

At every step
Modify the end pointers after breaking the existing links accoringly

Then at end, join the start end to large start
If start end is null return large start

Links

https://leetcode.com/problems/partition-list/description/

Video Links

Approach 1:

Pointer change

C++

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode *trav=head;
        ListNode *temp, *ss=nullptr, *se=nullptr, *ls=nullptr, *le=nullptr;

        while(trav != nullptr){
            if(trav->val < x){
                if(ss == nullptr)
                    ss = se = trav;

                else{
                    se->next = trav;
                    se = trav;
                }

                temp = se->next;
                se->next = nullptr;
                trav = temp;
            }

            else{
                if(ls == nullptr)
                    ls = le = trav;

                else{
                    le->next = trav;
                    le = trav;
                }
                
                temp = le->next;
                le->next = nullptr;
                trav = temp;
            }
        }

        if(ss == nullptr)
            return ls;

        se->next = ls;
        return ss;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++