How to find mid of a linked list


Category: Data Structure And Algorithms Tags: C#

 

Write a program to find mid element from a given linked list. Suppose linked list is as below:

Head -> 1 -> 2 -> 3 -> 4 -> 5

Output

Middle node of given linked list is: 3

 


Like 0 People
Asked on 20 June 2021
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 146
Questions: 16
Given Best Solutions: 16 *

Answers:

Nikhil Joshi

1. Using two pointers

We can have two pointers normal moving and fast moving pointer(moves twice as much as normal pointer). Once fast moving pointer reaches end, normal moving pointer ends up in mid and that is out answer.

static Node MidOfLinkedListUsingTwoPointers(Node head)
{
    Node normalPointer = head;
    Node fastPointer = head;

    while (fastPointer != null && fastPointer.Next != null)
    {
        fastPointer = fastPointer.Next.Next;
        normalPointer = normalPointer.Next;
    }
    return normalPointer;
}

Lets run above code:

static void Main(string[] args)
{
    Node head = new Node(1);
    head.Next = new Node(2);
    head.Next.Next = new Node(3);
    head.Next.Next.Next = new Node(4);
    head.Next.Next.Next.Next = new Node(5);

    Node middleNode = MidOfLinkedListUsingTwoPointers(head);

    Console.WriteLine($"Middle node of given linked list is: " + middleNode.Value);
}

Output

Middle node of given linked list is: 3

2. Counting length of linked list

We can first count the length of linked list by iterating it till end and then iterate it next time until the half of the count.

static Node MidOfLinkedListUsingLenght(Node head)
{
    Node temp = head;
    int count = 0;

    while (temp != null)
    {
        temp = temp.Next;
        count++;
    }

    var mid = count / 2;
    temp = head;

    while (mid > 0)
    {
        temp = temp.Next;
        mid--;
    }
    return temp;
}
static void Main(string[] args)
{
    Node head = new Node(1);
    head.Next = new Node(2);
    head.Next.Next = new Node(3);
    head.Next.Next.Next = new Node(4);
    head.Next.Next.Next.Next = new Node(5);

    Node middleNode = MidOfLinkedListUsingLenght(head);

    Console.WriteLine($"Middle node of given linked list is: " + middleNode.Value);
}

Output

Middle node of given linked list is: 3

Like 0 People on 20 June 2021

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x