How to find mid of a linked list

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