Find the middle element of a singly-linked list in a single pass

Problem Overview

Given a singly linked list, find the middle element of the linked list in a single pass.

Example 1

  • Input: 1 -> 2 -> 3 -> 4 -> 5
  • Output: 3

Example 2

  • Input: 5 -> 9 -> 7 -> 4
  • Output: 7

Take the 2nd mid element if there are an even number of elements in the list.

Algorithm

The algorithm to use here is the two-pointer technique.

The steps of the algorithm are as follows:

  1. Initialize slow_ptr and fast_ptr to the head node.
  2. Move the slow_ptr by one node and the fast_ptr by two nodes until the fast_ptr reaches the end of the list.

Once the fast_ptr reaches the end of the list, slow_ptr will point to the middle node of the list.

  • Time Complexity: O(N)
  • Space Complexity: O(1)

Code example

public class Main{
static class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
static class SinglyLinkedList{
Node head;
public SinglyLinkedList() {
this.head = null;
}
public void addFront(int data){
Node node = new Node(data);
node.next = head;
head = node;
}
public void printList(){
Node temp = head;
while(temp != null) {
System.out.print(temp.data + " - ");
temp = temp.next;
}
System.out.println("NULL");
}
public Node getMiddleElement(){
if(head == null) {
System.out.println("Empty list. Add elements to find the middle element");
return null;
}
Node slowPtr = head;
Node fastPtr = head;
while(fastPtr != null && fastPtr.next != null){
slowPtr = slowPtr.next;
fastPtr = fastPtr.next.next;
}
return slowPtr;
}
}
public static void main(String[] args) {
SinglyLinkedList sll = new SinglyLinkedList();
sll.addFront(5);
sll.addFront(4);
sll.addFront(3);
sll.addFront(2);
sll.addFront(1);
sll.printList();
System.out.println("Middle element for odd number of nodes in list is " + sll.getMiddleElement().data);
System.out.println("----");
sll = new SinglyLinkedList();
sll.addFront(4);
sll.addFront(7);
sll.addFront(9);
sll.addFront(5);
sll.printList();
System.out.println("Middle element for even number of nodes in list is " + sll.getMiddleElement().data);
}
}

Explanation

  • Lines 3-11: Node class is defined that contains the data and the next pointer.
  • Lines 14-51: SinglyLinkedList class is defined.
  • Line 15: The head pointer is defined.
  • Lines 21-25: addFront() method is defined where we add a new node in the beginning of the list.
  • Lines 27-34: printList() method is defined where the contents of the list are printed.
  • Lines 36-50: getMiddleElement() method is defined where the algorithm defined above is implemented to find the middle element.
  • Lines 55-63: We create a linked list of odd number of nodes and find the middle element of the list.
  • Lines 65-73: We create a linked list of even number of nodes and find the middle element of the list.

Free Resources