Related Tags

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

abhilash

### 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;
}
}

}

Node node = new Node(data);
}

public void printList(){
while(temp != null) {
System.out.print(temp.data + " - ");
temp = temp.next;
}
System.out.println("NULL");
}

public Node getMiddleElement(){
System.out.println("Empty list. Add elements to find the middle element");
return null;
}

while(fastPtr != null && fastPtr.next != null){
slowPtr = slowPtr.next;
fastPtr = fastPtr.next.next;
}

return slowPtr;
}
}

public static void main(String[] args) {

sll.printList();
System.out.println("Middle element for odd number of nodes in list is " + sll.getMiddleElement().data);

System.out.println("----");

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.

RELATED TAGS

CONTRIBUTOR

abhilash
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time 