ronith
7/7/2018 - 4:49 AM

Find the middle of a given linked list

Given a singly linked list, find middle of the linked list

Traverse linked list using two pointers. Move one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list.

Find the middle of a given linked list.cpp
content_copyfile_download
//https://www.geeksforgeeks.org/find-length-of-loop-in-linked-list/
#include<iostream>
#include<list>
using namespace std;

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

node* insert(node* head, int n) {
    node* list = (node*)malloc(sizeof(node*));
    list->data=n;
    list->next=head;
    head=list;
    return head;
}

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

void FindMiddle (node* head) {
    node *slow=head, *fast=head;
    if (head != NULL) {
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        cout<< "Middle node is "<< slow->data;
    }
}

int main() {
    int n;
    node* head = NULL;
    while (true) {
        cout<< "Enter the element, enter -9 to stop: ";
        cin>>n;
        if (n==-9)
            break;
        else
            head = insert(head,n);
    }
    print (head);
    FindMiddle (head);
}