Write a Program to Find the Middle Element of Linked List

Algorithm To Find the Middle Element of Linked List

1. Take two pointers.  Move first pointer by one and second pointer by two.

2. When second pointer reaches at end. First pointer reach at middle.

3. Print the value of first pointer which is the middle element.


Related Linked List Questions

Program to Reverse a Linked List

Program to Insert Node at the end of Linked List

Program to Find the Middle Element of Linked List

#include <stdio.h>

struct node{

    int data;
    struct node* next;

};

struct node* head;

void insert(int data){

    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = data;
    temp->next = head;
    head = temp;
}

void middle(){

    // Two pointers
    struct node* slow = head;
    struct node* fast = head;
    
    while(fast!=NULL && fast->next!=NULL){

        slow = slow->next;  // Move slow pointer by one
        fast = fast->next->next; // Move fast pointer by two
    }
    printf("\nmiddle element is %d",slow->data);

}

void print(){

   struct node* temp = head;

    while(temp!=NULL){
        printf("%d\n",temp->data);
        temp = temp->next;
    
    }
    
}


void main(){

    head = NULL;

   

    insert(2);
    insert(4);
    insert(6);
    insert(7);
    insert(8);
 
    print();
    middle();


}

Write a Program/Code to Reverse a Linked List

Assume you have a linked list

Input - 1->4->5->6

Output - 6->5->4->1

In Input head points to a node whose value is 1 and the address node which contains 6 point to NULL.

In Output things are just reversed head point to node whose value is 6 and node which has value 1 points to NULL.

Image taken from studentduniya.in

Algorithm to Reverse a Linked List

1. First we need to traverse a linked list.

2. Reverse a links means the address node points to next node to prev, prev to current and current to next.

Program to Reverse a Linked List

#include <stdio.h>

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

struct node* head;

void insert_node(int data){
    
    struct node* newnode=(struct node*)malloc(sizeof(struct node*));
    newnode->data = data;
    newnode->next = head;
    
    head = newnode;
}

void reverse_node(){
    
    struct node *prev,*next,*current;
    current = head;
    
    while(current!=NULL){
        
        next = current->next;
        current->next = prev;
        prev = current;
        current=next;
    }
    head = prev;
    
}

void print(){
    
    struct node* p;
    p = head;
    
    while(p!=NULL){
        printf("%d\n",p->data);
        p=p->next;
    }
    printf("\n");
}

Void main()
{

  head = NULL;

  insert_node(6);
  insert_node(5);
  insert_node(4);
  insert_node(1);

  print();
  reverse_node();
  print();

}

Problem on Linked List

Best Books on Data Structures

Data Structure Books Available on Flipkart

Data Structure Books Available on Amazon India

Data Structure Books on Amazon

Write a C++ Program to insert a node at the tail of a linked list

C++ Program to insert a node at the tail of a linked list

Logic of Program

1. If no node is inserted, insert the element at the beginning,

2. If head is not null, then traverse the linked list and insert the node at the end.

#include<iostream>
#include<cstdio>
#include<cstdlib>

using namespace std;

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


Node* Insert(Node *head,int data)
{
  
    Node *p,*tmp;
    
    Node* temp = (Node*)malloc(sizeof(Node));

    temp->data = data;
   
    // If head is NULL, means first element
 
    if(head == NULL){

       temp->next = NULL;
       head = temp;

    } else {
        
         p =head;

        // Traverse the linked list and insert at the end

        while(p->next!=NULL){
          p = p->next;
        }

        // Last link point to inserted element
   
        p->next = temp;
    
        temp->next = NULL;
    }
    
    return head;
}

void Print(Node *head)
{
 Node *temp = head;
 while(temp!= NULL)
         { cout<<temp->data<<"\n";
           temp = temp->next;
         }
}


int main()
{
 
 Node *head = NULL;
 
 head = Insert(head,3);
 head = Insert(head,5);
 head = Insert(head,2);
 head = Insert(head,7);
 
 Print(head);
}

Write a C++ Program to insert a node at head of a linked list

C++ Program to insert a node at head of a linked list

In my previous post, i explain what is the advantage of linked list over arrays. Why we prefer linked list. 

C Program to insert a node at the beginning/head of a linked list

//

#include <iostream>
#include<cstdio>
#include<cstdlib>

using namespace std;

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

// Insert node at the beginning

Node* Insert(Node *head,int data)
{
  
    Node *temp=(Node*)malloc(sizeof(struct Node));
    temp->data = data;
    temp->next = head;
    
    head = temp;
    
    return head;

}

void Print(Node *head)
{
 Node *temp = head;

        // Traverse and print the value

 while(temp!= NULL){

              cout<<temp->data<<"\n";

              temp = temp->next;

         }
}


int main()
{
 
 Node *head = NULL;

        head = Insert(head,5);

        head = Insert(head,2);

        head = Insert(head,3);

 Print(head);
}

Write a C Program to count the number of occurrences of an element in a single linked list

C Program to count the number of occurrences of an element in a single linked list

Logic

1. Traverse the linked list.

2. Increment the count when data passed is equal to traverse element .

// Program

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

// Created node

struct node{

        int data;
        struct node* next;
};

void insertLinkedList(struct node** head,int value){

        struct node* temp = (struct node*) malloc(sizeof(struct node));

        temp->data = value;
        temp->next = (*head);
        (*head) = temp;

}

void countElement(struct node* head,int element){
    
        int count=0;

        while(head!=NULL){
                if(head->data == element){
                        count++;
                        head = head->next;
                }   
        }   

        printf("Count of an element is %d",count);

}


void main(){

        // Intialize the head node with NULL
                                                                                         struct node* head = NULL;

        insertLinkedList(&head,4);
        insertLinkedList(&head,6);
        insertLinkedList(&head,2);
        insertLinkedList(&head,4);

        // Printing the count of an element


        countElement(head,4);


}

Write a C Program to Insert a Node at the Head/Beginning of a Linked List

In my previous post, i mentioned the advantage of linked list. In this post i am showing how to insert a node at the beginning of a linked list.

Program to Insert a Node at the Head/Beginning of a Linked List

// Program

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

// Declare the Node

struct Node{

        int data;
        struct Node* next;
        };  

struct Node* head;        

// Insert the node a the beginning of a linked list

void insert(int data){

        struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
        temp->data = data;
        temp->next = head;
        head = temp;

}

void print(){

        struct Node* temp = head;
    
        while(temp!=NULL)
        {   
             printf("%d",temp->data);
             temp = temp->next;
             printf("\n");
        }   
}

int main()
{

        head = NULL;
        insert(4);
        insert(5);
        insert(6);
        print();
}