Split nodes of a linked list into the front and back halves in C

Split nodes of a linked list into two halves

Problem statement: Given a linked list split it into two halves, front and back. If the linked list has even number of elements then resultant linked lists will be equal. If the input linked list has odd number of elements then front linked list will has one element more than back linked list.


/*C code to Split nodes of a linked list into the 
front and back halves*/
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int data;
    struct node *next;
} NODE;

NODE *newNode(int key)
{
    NODE *temp = (NODE *)malloc(sizeof(NODE));
    temp->data = key;
    temp->next = NULL;
    return temp;
}

void splitInHalf(NODE *head, NODE **front, NODE **end)
{
    if (head == NULL)
    {
        *front = head;
        *end = NULL;
        return;
    }
    NODE *slow = head, *fast = head;

    if (head != NULL)
    {
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
    }

    *front = head;
    *end = slow->next;
    slow->next = NULL;
}

void printList(NODE *temp)
{
    if (temp == NULL)
    {
        printf("List is empty!\n");
        return;
    }
    
    while (temp != NULL)
    {
        printf("%d--> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main()
{
    NODE *head = NULL;
    NODE *front = NULL;
    NODE *end = NULL;

    head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
    head->next->next->next->next->next = NULL;

    printf("Linked List is\t");
    printList(head);

    splitInHalf(head, &front, &end);

    printf("\nFront half linked list is\t");
    printList(front);
    
    printf("\nEnd half linked list is\t\t");
    printList(end);

    return 0;
}

$ gcc splitHalf.c
$ ./a.out
Linked List is 1–> 2–> 3–> 4–> 5–> NULL
Front half linked list is 1–> 2–> 3–> NULL

End half linked list is 4–> 5–> NULL$

If you like the post Split nodes of a linked list into two halves, please share your feedback!

also see

C Programming language
Go Programming language
Linked List Array
Simplification Queue
DBMS Reasoning
Aptitude HTML
Previous articleCount the triplets in C
Next articleConditional Flow Control Structures in C

LEAVE A REPLY

Please enter your comment!
Please enter your name here