Given a singly linked list, find the middle element of the linked list in a single pass.
Example 1
1 -> 2 -> 3 -> 4 -> 5
3
Example 2
5 -> 9 -> 7 -> 4
7
Take the 2nd mid element if there are an even number of elements in the list.
The algorithm to use here is the two-pointer technique.
The steps of the algorithm are as follows:
slow_ptr
and fast_ptr
to the head node.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.
O(N)
O(1)
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);}}
Node
class is defined that contains the data
and the next
pointer.SinglyLinkedList
class is defined.head
pointer is defined.addFront()
method is defined where we add a new node in the beginning of the list.printList()
method is defined where the contents of the list are printed.getMiddleElement()
method is defined where the algorithm defined above is implemented to find the middle element.