Partition List – preserve the original relative order of the nodes using c

In this tutorial, i will show you how to partition a linked list using a value x such that all nodes less than x come before nodes greater than or equal to x and we are to preserve the original relative order of the nodes in each of the two partitions.

This question is posted in leetcode here: https://leetcode.com/problems/partition-list/ and the i have used recursion to solve it because i needed to take advantage of the power of backtracking to be able to preserve the original relative order of the nodes; not just that, just continue reading for the final idea to preserve the order of the nodes.

So basically what i have done in the code below is to create two new nodes NH1 and NH2. I first of all traverse the given linked list from the head node to the last node using recursion – of course the base case is when i reach NULL, then during backtracking i check the value of the current node against the given value x; if x > currentnodes->value, i create a new node, assign the value of the currentnode to the new node and then insert the new node at the head position of NH1 otherwise i insert the new node at the head position of NH2. Inserting the new node at the head position of either NH1 or NH2 is the final idea to preserve the order of the nodes in each of the two partitions. Finally i merge the last node of NH1 to the head node of NH2 and that’s it.

Implementation in c

struct ListNode {//node structure
    int val;
    struct ListNode *next;
};

struct ListNode *NH1 = NULL;//create node for holding values lesser than 3
struct ListNode *NH2 = NULL;//create node for holding values greater than 3

struct ListNode* partition(struct ListNode** head, int x){
    static int countt = 0, btractCnt = 0;
    if(*head == NULL){
        return 0;
    }else{
        if(countt == 0){//get count of nodes in given list
            struct ListNode *temp = *head;
            while(temp != NULL){
                temp = temp->next;
                countt++;
            }
        }

        struct node *H = (*head)->next;
        partition(&H, x);//recurse
        btractCnt++;
        if(x > (*head)->val){//compare x against given list nodes val
            struct ListNode *newnode = malloc(sizeof(struct ListNode));
            newnode->val = (*head)->val;
            if(NH1 == NULL){
                newnode->next = NULL;
                NH1 = newnode;
            }else{
                newnode->next = NH1;
                NH1 = newnode;
            }
        }else{
            struct ListNode *newnode = malloc(sizeof(struct ListNode));
            newnode->val = (*head)->val;
            if(NH2 == NULL){
                newnode->next = NULL;
                NH2 = newnode;
            }else{
                newnode->next = NH2;
                NH2 = newnode;
            }
        }

        if(btractCnt == countt){//done comparing x against given list nodes val
            struct ListNode *temp1;//temporary node for traversal
            struct ListNode *Hp;//create heap pointer for NH1
            Hp = temp1 = NH1;//initialize temp node and head pointer

            while(temp1->next != NULL)//get to the lastnode of NH1
                temp1 = temp1->next;

            temp1->next = NH2;//merge the two new linked list
            NH1 = Hp;//mark the head node after merge
        }
    }
    return 0;
}

void Print_List(struct ListNode **head){
    struct ListNode *temp = *head;
    while(temp != NULL){
        printf("%d ", temp->val);
        temp = temp->next;
    }
    free(temp);
    return 0;
}

int main(){
    //create the list
    struct ListNode *n1,*n2,*n3,*n4,*n5,*n6;
    n1 = malloc(sizeof(struct ListNode));
    n2 = malloc(sizeof(struct ListNode));
    n3 = malloc(sizeof(struct ListNode));
    n4 = malloc(sizeof(struct ListNode));
    n5 = malloc(sizeof(struct ListNode));
    n6 = malloc(sizeof(struct ListNode));
    
    //assign values to nodes
    n1->val = 1;
    n2->val = 4;
    n3->val = 3;
    n4->val = 2;
    n5->val = 5;
    n6->val = 2;
    n6->next = NULL;
    
    //connect nodes
    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n5;
    n5->next = n6;

    partition(&n1, 3);//partition list by the value 3
    Print_List(&NH1);//print partitioned list
}
Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.

You May Also Like