Open In App

C Program For Segregating Even And Odd Nodes In A Linked List

Last Updated : 28 Dec, 2022
Comments
Improve
Suggest changes
Like Article
Like
Report

Given a Linked List of integers, write a function to modify the linked list such that all even numbers appear before all the odd numbers in the modified linked list. Also, keep the order of even and odd numbers the same.

Examples: 

Input: 17->15->8->12->10->5->4->1->7->6->NULL
Output: 8->12->10->4->6->17->15->5->1->7->NULL

Input: 8->12->10->5->4->1->6->NULL
Output: 8->12->10->4->6->5->1->NULL

// If all numbers are even then do not change the list
Input: 8->12->10->NULL
Output: 8->12->10->NULL

// If all numbers are odd then do not change the list
Input: 1->3->5->7->NULL
Output: 1->3->5->7->NULL

Method: 
The idea is to get pointer to the last node of list. And then traverse the list starting from the head node and move the odd-valued nodes from their current position to end of the list.
Thanks to blunderboy for suggesting this method. Algorithm: 

  1. Get pointer to the last node.
  2. Move all the odd nodes to the end.
    • Consider all odd nodes before the first even node and move them to end.
    • Change the head pointer to point to the first even node.
    • Consider all odd nodes after the first even node and move them to the end. 

Below is the implementation of the above approach:

C
// C program to segregate even and 
// odd nodes in a Linked List
#include <stdio.h>
#include <stdlib.h>

// A node of the singly linked list 
struct Node
{
    int data;
    struct Node *next;
};

void segregateEvenOdd(struct Node **head_ref)
{
    struct Node *end = *head_ref;
    struct Node *prev = NULL;
    struct Node *curr = *head_ref;

    // Get pointer to the last node 
    while (end->next != NULL)
        end = end->next;

    struct Node *new_end = end;

    /* Consider all odd nodes before the 
       first even node and move then after 
       end */
    while (curr->data % 2 != 0 && 
           curr != end)
    {
        new_end->next = curr;
        curr = curr->next;
        new_end->next->next = NULL;
        new_end = new_end->next;
    }

    // 10->8->17->17->15
    /* Do following steps only if there 
       is any even node */
    if (curr->data % 2 == 0)
    {
        /* Change the head pointer to point 
           to first even node */
        *head_ref = curr;

        /* Now current points to the first 
           even node */
        while (curr != end)
        {
            if ( (curr->data) % 2 == 0 )
            {
                prev = curr;
                curr = curr->next;
            }
            else
            {
                /* Break the link between prev 
                   and current */
                prev->next = curr->next;

                // Make next of curr as NULL  
                curr->next = NULL;

                // Move curr to end 
                new_end->next = curr;

                // Make curr as new end of list 
                new_end = curr;

                /* Update current pointer to next 
                   of the moved node */
                curr = prev->next;
            }
        }
    }

    /* We must have prev set before executing 
       lines following this statement */
    else prev = curr;

    /* If there are more than 1 odd nodes and 
       end of original list is odd then move 
       this node to end to maintain same order 
       of odd numbers in modified list */
    if (new_end != end && 
       (end->data) % 2 != 0)
    {
        prev->next = end->next;
        end->next = NULL;
        new_end->next = end;
    }
    return;
}

// UTILITY FUNCTIONS 
/* Function to insert a node at 
   the beginning  */
void push(struct Node** head_ref, 
          int new_data)
{
    // Allocate node 
    struct Node* new_node =
           (struct Node*) malloc(sizeof(struct Node));

    // Put in the data  
    new_node->data = new_data;

    // Link the old list off the new node 
    new_node->next = (*head_ref);

    // Move the head to point to the new node 
    (*head_ref) = new_node;
}

// Function to print nodes in 
// a given linked list 
void printList(struct Node *node)
{
    while (node!=NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}

// Driver code
int main()
{
    // Start with the empty list 
    struct Node* head = NULL;

    /* Let us create a sample linked list 
       as following 0->2->4->6->8->10->11 */
    push(&head, 11);
    push(&head, 10);
    push(&head, 8);
    push(&head, 6);
    push(&head, 4);
    push(&head, 2);
    push(&head, 0);

    printf("Original Linked list ");
    printList(head);

    segregateEvenOdd(&head);

    printf("Modified Linked list ");
    printList(head);

    return 0;
}

Output
Original Linked list 0 2 4 6 8 10 11 Modified Linked list 0 2 4 6 8 10 11 

Time complexity: O(n)
Auxiliary space: O(1) as it is using constant space


Please refer complete article on Segregate even and odd nodes in a Linked List for more details!


Next Article
Practice Tags :

Similar Reads

  翻译: