Partitioning a linked list around a given value and keeping the original order

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Proper understanding of concepts based on Linked Lists can give you an edge in a coding interview.

Problem Statement

In this problem, given a linked list and a value X, we are required to partition it such that all nodes less than X come before nodes greater than or equal to x.

Note: You should maintain the original relative order of the nodes in each of the two partitions.

Problem Statement Understanding

Let’s understand the problem statement with help of examples.

If the given linked list is:

It means that we have to move all nodes smaller than 3 before the nodes having values greater than or equal to 3. Also, while partitioning the linked list around value 3, the original relative order of the nodes in each of the two partitions should be maintained.

So our final resultant linked list after partitioning will look like:

This statement maintains the original relative order of the nodes in each of the two partitions implies that while partitioning, the nodes in each of the two partitions should be in the same order as they are present in the original linked list.

  • From the above linked list, we can see that 1, 2 and 2 will come in the first partition(nodes smaller than X) and 4, 3 and 7 will come in the second partition(nodes greater than or equal to X).
  • If we carefully compare the resultant linked list and the original linked list we can clearly see that 1, 2 and 2, the nodes of first partition are in the same order in the resultant list as they were in the original linked list (2 is occurring after 1 and another 2 is occurring after 2). Similarly, the nodes of the second partition 4, 3 and 7 are also in the same order as they were in the original linked list (3 is occurring after 4 and another 5 is occurring after 3).

Explanation: In the resultant linked list, first there will be the elements of the first partition (elements or nodes smaller than X) and then there will be the elements of the second partition (elements greater than or equal to X). Also, both the partitions will preserve the order from the original linked list.

Now I think from the above example the problem is clear, we will have to now think of how we can approach this problem.

Approach

As we need all the nodes having value smaller than X before nodes having value greater than or equal to X, so we will have to divide the original linked list into two sections:

  • A list of nodes with values less than X and,
  • A list of nodes with values higher than or equal to X.

Then, after diving the original linked list, we'll use pointers to stitch them back together after the division such that all the nodes having smaller value than X comes before nodes having greater value of equal to X.

The algorithm in brief:

We will traverse the original linked list as normal, and we will select in which linked list a node should belong to based on its value.

  • If a node's value is less than X, it will be appended to the low-container list, which keeps track of nodes with values less than X.
  • Otherwise, it will be appended to the high-container list, which keeps track of nodes with values greater than or equal to X.

Finally, after traversing, we'll sew the end node of the first linked list (the low-container list) to the head node of our second list (the high-container list). This way, we can maintain the order of elements in the list.

After the complete traversal of the original linked list, the low-container list will have all the nodes having value smaller than X, while the high-container list will have all the nodes having values greater than or equal to X.

A few buffers will be required to maintain track of the partitioned lists.

  • new_Head: Head of the new modified linked list.
  • low_Head: Head of low-container linked list.
  • high_Head: Head of high-container linked list.
  • less: A pointer that will help us in linking every node with the value lower than X together, this way we will get the low-container list. It will act as an iterator for the low-container linked list.
  • more: A pointer which will help us in linking every node with the value higher or equal to the X together, this way we will get the high-container list. It will act as an iterator for the high-container linked list.

Algorithm

  • Check if head == NULL, If true, return NULL.
  • Initialize new_Head, low_Head, high_Head, less and more to NULL.
  • Begin iterating the original linked list. We'll try to make two distinct linked lists (low-container list and high-container list) out of the original linked list by just changing the links.
  • While traversing the original linked list:
    • If a node is having value smaller than X, it will get appended to the end of low-container list.
    • If a node is having value greater than or equal to X, it will get appended to the end of high-container list.
  • Once the traversal of the original linked list is over, the low-container list will be a list having all the nodes with values smaller than X and the high-container list will contain all the nodes from the original list having values greater than or equal to X.
  • The heads of the two linked lists above will both point to the first node of their own lists.
  • Finally, all that remains is to stitch the lists back together. The low-container linked list's last node should point to the head of the high-container linked list.
  • We will return the head of high-container list if the low-container list does not exist (the original linked list does not contains any nodes with a value less than X) and if the low-container list exists we will make new_Head point to head of low-container(low_Head) and will return new_Head.

The problem has been solved only by adjusting the links.

Dry Run



Code Implementation

#include 
using namespace std;

// Structure of a node
struct node{
    int val;
    struct node* next;
    node(int x){
        val=x;
        next=NULL;
    }
};


// Return pointer to the produced list.
struct node* orderOfList(struct node* head,int x){
    if(!head)return head;  
// return NULL if the linked list is empty
    
// Head of the modified list
    struct node* new_Head = NULL; 
// Head of low-container list partition
    struct node* low_Head = NULL;   
// Head of high-container list partition
    struct node* high_Head = NULL; 
// Itearator of low-container list. 
    struct node* less = NULL;  
//  Iterator of high-container list.    
    struct node* more = NULL;    
             
// traverse through the list.
    while(head){            
        if(head->val < x){          
/* If the node's value is less than x,
it should go in low-container.
              
If we haven't set the head of low-container
Then, low_Head will be the head.*/
            if(!low_Head){          
                low_Head = head;     
// and also point the iterator to the beginning.
                less = low_Head;         
            }else{
                less->next = head;   
/* If the low_Head is already initialized, we are required to point the iterator to point to this node*/
                less = head;     
            }
            
        }else{
        
            if(!high_Head){           
/* initialize if the head of the high-container has not been initialized yet.  
and point the 'more' iterator to the beginning
which is high_Head.*/
                high_Head = head;
                more = high_Head;  
            }else{ 
/* If high_Head already initialized,
point the next field of last node in this list to head*/
                more->next = head; 
// updating the iterator
                more = head;
            }
        }
        head = head->next; 
// Update the iterator of the original list.
    }
    if(low_Head == NULL){ 
/* If the first partition of the linked list(low-container) is empty, we just return the high_Head.
 Also point the last node's next to NULL.*/
        new_Head = high_Head;
        more->next = NULL;  
    }else{ 
/* if the low_head list exists
point the new_Head to low_Head*/
        new_Head = low_Head; 
/* last node of the low-container should
point to the high-container's head.*/
        less->next = high_Head; 
        if(high_Head){         
            more->next = NULL;
        }
    }
    return new_Head;   
}

// To traverse through the linked list
void list_traversal(struct node* head){
    while(head){                       
        cout<val<<" ";
        head = head->next;
    }
}
int main() {
    
    struct node* head = new node(1);
    head->next = new node(4);
    head->next->next = new node(3);
    head->next->next->next = new node(2);
    head->next->next->next->next = new node(7);
    head->next->next->next->next->next = new node(2);
    int x = 3; 
    
    struct node* new_Head = orderOfList(head,x);
    list_traversal(new_Head);
    return 0;
}

Output

1→2→2→4→3→7

Time Complexity: O(N) – we are traversing through the original linked list and only creating 2 linked lists out of it.

In this article, we have tried to solve the problem of partitioning a linked list around a given value while maintaining the original order. This problem is interesting as well as important from the interview’s point of view. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Advantages and Disadvantages of Linked List
Next post Delete middle of linked list

Leave a Reply

Your email address will not be published. Required fields are marked *