Display the middle element of a linked list

  • Two-Pass:
    1. The basic way we can do this is by counting the number of elements in the linked list in one pass, say it comes out to be n.
    2. n/2 will be the middle element and again we would need to traverse till n/2 to get to the middle element and then display it.
  • One Pass:
    1. Create two pointers slow and fast.
    2. Move the fast pointer two nodes at a time & slow pointer one node at a time.
    3. Check when the linked part of the fast pointer becomes NULL (odd number of nodes) or the fast pointer becomes NULL (even number of nodes), at that point slow pointer points to the middle element
#include <iostream>
#include <stdio.h>
using namespace std;

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

Node *head = NULL;
//Function to reverse linked list
void reverseList()
{
    Node *prev, *current, *n;
    prev = NULL;
    current = head;

    while (current != NULL)
    {
        n = current->next;
        current->next = prev;
        prev = current;
        current = n;
    }
    head = prev;
}
int countNodes()
{
    Node *ptr = new Node();
    int count = 0;
    while (ptr != NULL)
    {
        ptr = ptr->next;
        count++;
    }
    return count;
}

//Function to insert at the end of linked list

void insertEnd(int a)
{
    Node *ptr = new Node();
    ptr->data = a;
    ptr->next = NULL;

    if (head == NULL)
    {
        head = ptr;
    }
    else
    {
        Node *temp = head;
        while (temp->next != NULL)
        {
            temp = temp->next;
        }
        temp->next = ptr;
    }
}

//Make A loop
void makeloop(int k)
{
    struct Node *temp = head;
    int count = 1;
    while (count < k)
    {
        temp = temp->next;
        count++;
    }
    struct Node *joint_point = temp;
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = joint_point;
}

//Function to display linked list

void displayList(int total_nodes)
{

    Node *temp = head;
    int count = 0;
    while (count < total_nodes)
    {
        cout << temp->data << " ";
        count++;
        temp = temp->next;
    }
    cout << "\n";
}

struct Node *creatnode(int d)
{
    struct Node *temp = new Node();
    temp->data = d;
    temp->next = NULL;
    return temp;
}
void check_loop(int total_nodes)
{
	int count =0;
	if(count < total_nodes)
	{
	count++;
	Node *p =head;
	Node *q=head;
	while(p&&q&&q->next)
	{
		p=p->next;
		q=q->next->next;
		if(p=q)
		{
			cout<<"loop";
		}
		cout<<"No Loop";
	}
}
}

Node* startloop(Node *p)
{
    
}
int main()
{
    int total_nodes;
    insertEnd(1);
    insertEnd(2);
    insertEnd(3);
    insertEnd(4);
    insertEnd(5);
    insertEnd(6);
    insertEnd(7);
    insertEnd(8);
    insertEnd(9);
    insertEnd(10);
    total_nodes = countNodes();
    cout<<"total nodes"<<total_nodes;
    cout << "1st";
    displayList(10);
    makeloop(5);
    reverseList();
    cout << "dkjfgsdkuf0"<<endl;
    displayList(10);
    check_loop(10);
    return 0;
}
  • Two-Pass:
    1. The basic way we can do this is by counting the number of elements in the linked list in one pass, say it comes out to be n.
    2. n/2 will be the middle element and again we would need to traverse till n/2 to get to the middle element and then display it.
  • One Pass:
    1. Create two pointers slow and fast.
    2. Move the fast pointer two nodes at a time & slow pointer one node at a time.
    3. Check when the linked part of the fast pointer becomes NULL (odd number of nodes) or the fast pointer becomes NULL (even number of nodes), at that point slow pointer points to the middle element
#include <iostream>
#include <stdio.h>
using namespace std;

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

Node *head = NULL;
//Function to reverse linked list
void reverseList()
{
    Node *prev, *current, *n;
    prev = NULL;
    current = head;

    while (current != NULL)
    {
        n = current->next;
        current->next = prev;
        prev = current;
        current = n;
    }
    head = prev;
}
int countNodes()
{
    Node *ptr = new Node();
    int count = 0;
    while (ptr != NULL)
    {
        ptr = ptr->next;
        count++;
    }
    return count;
}

//Function to insert at the end of linked list

void insertEnd(int a)
{
    Node *ptr = new Node();
    ptr->data = a;
    ptr->next = NULL;

    if (head == NULL)
    {
        head = ptr;
    }
    else
    {
        Node *temp = head;
        while (temp->next != NULL)
        {
            temp = temp->next;
        }
        temp->next = ptr;
    }
}

//Make A loop
void makeloop(int k)
{
    struct Node *temp = head;
    int count = 1;
    while (count < k)
    {
        temp = temp->next;
        count++;
    }
    struct Node *joint_point = temp;
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = joint_point;
}

//Function to display linked list

void displayList(int total_nodes)
{

    Node *temp = head;
    int count = 0;
    while (count < total_nodes)
    {
        cout << temp->data << " ";
        count++;
        temp = temp->next;
    }
    cout << "\n";
}

struct Node *creatnode(int d)
{
    struct Node *temp = new Node();
    temp->data = d;
    temp->next = NULL;
    return temp;
}
void check_loop(int total_nodes)
{
	int count =0;
	if(count < total_nodes)
	{
	count++;
	Node *p =head;
	Node *q=head;
	while(p&&q&&q->next)
	{
		p=p->next;
		q=q->next->next;
		if(p=q)
		{
			cout<<"loop";
		}
		cout<<"No Loop";
	}
}
}

Node* startloop(Node *p)
{
    
}
int main()
{
    int total_nodes;
    insertEnd(1);
    insertEnd(2);
    insertEnd(3);
    insertEnd(4);
    insertEnd(5);
    insertEnd(6);
    insertEnd(7);
    insertEnd(8);
    insertEnd(9);
    insertEnd(10);
    total_nodes = countNodes();
    cout<<"total nodes"<<total_nodes;
    cout << "1st";
    displayList(10);
    makeloop(5);
    reverseList();
    cout << "dkjfgsdkuf0"<<endl;
    displayList(10);
    check_loop(10);
    return 0;
}

You might like

Leave a Reply

Your email address will not be published. Required fields are marked *