Program to find middle element of a Linked List

Given a linked list, write a program to find middle element of a linked list. e.g.- for linked list 1 -> 2 -> 3 -> 4 -> 5, output should be 3.

linked list middle element

Problem -

Find the middle or centre element in a singly list.

Solutions-

Solution 1: We can use the naive approach by simply traversing the linked list and count the number of elements then divide the number of elements by 2.

Then go for a second loop and traverse for the half of the number of elements in the linked list. But in this approach, we have to use two loops for iterating over the linked list twice.

Solution 2: We may go for another solution which is to use two pointers on the linked list. The first pointer will be a slow pointer i.e., moves one step for every iteration and the second pointer will be the fast pointer which moves two steps for every iteration.

In the end, the linked list will be divided into parts and the fast pointer will be at the end of the linked list and the slow pointer will be at the middle of the linked list. We can achieve this by using one loop only. In this post, we will this approach to solve the problem.

Program

Python

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

class LinkedList:
  def __init__(self):
    self.head = None

  def insertAtEnd(self, data):
    node = Node(data)
    if self.head is None:
      self.head = node
    else:
      temp = self.head
      while temp.next:
        temp = temp.next
      temp.next = node

  def traverse(self):
    temp = self.head
    while temp:
      print(temp.data, end=' ')
      temp = temp.next
    print()

  def findCenterNode(self):
    ptr = self.head
    fastPtr = self.head
    while fastPtr and fastPtr.next:
      fastPtr = fastPtr.next.next
      # fastPtr = fastPtr.next
      ptr = ptr.next
    print(ptr.data)
  

linkedlist = LinkedList()
linkedlist.insertAtEnd(5)
linkedlist.insertAtEnd(1)
linkedlist.insertAtEnd(6)
linkedlist.insertAtEnd(8)
linkedlist.insertAtEnd(9)
linkedlist.insertAtEnd(4)
linkedlist.insertAtEnd(2)
print('Middle element is: ')
linkedlist.findCenterNode()

Java

class Node {
  int data;
  Node next;
  Node(int data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  Node head;
  LinkedList() {
    head = null;
  }

  public void insertAtEnd(int data) {
    if (head == null) {
      head = new Node(data);
    }
    else {
      Node temp = head;
      while (temp.next != null) {
        temp = temp.next;
      }
      temp.next = new Node(data);
    }
  }

  public void traverse() {
    Node temp = head;
    while (temp != null) {
      System.out.print(temp.data + " ");
      temp = temp.next;
    }
    System.out.println();
  }

  public void findCenterNode() {
    Node ptr = head;
    Node fastPtr = head;
    while (fastPtr != null && fastPtr.next != null) {
      fastPtr = fastPtr.next.next;
      ptr = ptr.next;
    }
    System.out.println(ptr.data);
  }
}

class Main {
  public static void main(String[] args) {
    LinkedList ll = new LinkedList();
    ll.insertAtEnd(5);
    ll.insertAtEnd(1);
    ll.insertAtEnd(6);
    ll.insertAtEnd(8);
    ll.insertAtEnd(9);
    ll.insertAtEnd(4);
    ll.insertAtEnd(2);
    System.out.println("Middle element is: ");
    ll.findCenterNode();
  }
}

Output

Middle element is:
8