w3resource

C Exercises: Split a singly linked list into two halves

C Singly Linked List : Exercise-32 with Solution

Write a C program to split a singly linked list into two halves.

Sample Solution:

C Code:

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

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

struct Node * newNode(int data) {
  struct Node * temp = (struct Node * ) malloc(sizeof(struct Node));
  temp -> data = data;
  temp -> next = NULL;
  return temp;
}
void printList(struct Node * head) {
  while (head != NULL) {
    printf("%d ", head -> data);
    head = head -> next;
  }
  printf("\n");
}

void splitList(struct Node * head, struct Node ** front_ref, struct Node ** back_ref) {
  struct Node * slow = head;
  struct Node * fast = head -> next;

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

  * front_ref = head;
  * back_ref = slow -> next;
  slow -> next = NULL;
}

int main() {
  struct Node * temp;
  struct Node * 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);

  printf("Original List: ");
  printList(head);
  struct Node * firstHalf = NULL;
  struct Node * secondHalf = NULL;

  // Calling the splitList method
  splitList(head, & firstHalf, & secondHalf);
  printf("Split the said singly linked list into halves:\n");
  printf("First half: ");
  temp = firstHalf;
  printList(temp);
  printf("Second half: ");
  temp = secondHalf;
  printList(temp);
  struct Node * head1 = newNode(1);
  head1 -> next = newNode(2);
  head1 -> next -> next = newNode(3);
  head1 -> next -> next -> next = newNode(4);
  head1 -> next -> next -> next -> next = newNode(5);
  head1 -> next -> next -> next -> next -> next = newNode(6);
  printf("\nOriginal List: ");
  printList(head1);
  firstHalf = NULL;
  secondHalf = NULL;

  // Calling the splitList method
  splitList(head1, & firstHalf, & secondHalf);
  printf("Split the said singly linked list into halves:\n");
  printf("First half: ");
  temp = firstHalf;
  printList(temp);
  printf("Second half: ");
  temp = secondHalf;
  printList(temp);
  return 0;
}

Sample Output:

Original List: 1 2 3 4 5 
Split the said singly linked list into halves:
First half: 1 2 3 
Second half: 4 5 

Original List: 1 2 3 4 5 6 
Split the said singly linked list into halves:
First half: 1 2 3 
Second half: 4 5 6

Flowchart :

Flowchart: Split a singly linked list into two halves.
Flowchart: Split a singly linked list into two halves.

C Programming Code Editor:

Previous: Reverse a singly linked list in pairs.
Next: Delete alternate nodes of a singly linked list.

What is the difficulty level of this exercise?



Follow us on Facebook and Twitter for latest update.