C Exercises: Partition a singly linked list around a specific value

C Singly Linked List : Exercise-21 with Solution

Write a C program to partition a singly linked list based on a specific value.

Sample Solution:

C Code:

#include<stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* new_Node(int data) {
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

// Function to partition a singly linked list around a value x
struct Node* partition_List(struct Node* head, int x) {
    struct Node* before_start = NULL;
    struct Node* before_end = NULL;
    struct Node* after_start = NULL;
    struct Node* after_end = NULL;
    struct Node* current = head;

    while (current) {
        if (current->data < x) {
            if (!before_start) {
                before_start = current;
                before_end = before_start;
            } else {
                before_end->next = current;
                before_end = current;
            }
        } else {
            if (!after_start) {
                after_start = current;
                after_end = after_start;
            } else {
                after_end->next = current;
                after_end = current;
            }
        }
        current = current->next;
    }

    if (before_start) {
        before_end->next = after_start;
        after_end->next = NULL;
        return before_start;
    } else {
        return after_start;
    }
}

// Function to display a linked list
void displayList(struct Node* head) {
    while (head) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

int main() {
    struct Node* list = new_Node(3);
    list->next = new_Node(5);
    list->next->next = new_Node(7);
    list->next->next->next = new_Node(5);
    list->next->next->next->next = new_Node(9);
    list->next->next->next->next->next = new_Node(2);
    list->next->next->next->next->next->next = new_Node(1);

    int x = 5;
    printf("Original list:\n", x);
    displayList(list);

    list = partition_List(list, x);
    printf("Linked List after partition around %d:\n", x);
    displayList(list);
    return 0;
}

Sample Output:

Original list:
3 5 7 5 9 2 1 
Linked List after partition around 5:
3 2 1 5 7 5 9 

Flowchart :

C Programming Code Editor:

Previous: Nodes from the end of a singly linked list.
Next: Add two numbers represented by linked lists.