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 |