Trusted answers to developer questions

Ravi

Given a singly linked list, find the middle node/element of the list in a single traversal.

Example 1:

- Input -
`1 -> 2 -> 3 -> 4 -> 5`

- Output -
`3`

Example 2:

- Input -
`1 -> 2 -> 3 -> 4`

- Output -
`3`

If the list contains an even number of nodes, two elements can be the middle elements. The second middle element has to be considered as the middle element. In Example 2, `2`

and `3`

can both be middle elements, but `3`

should be considered as the middle element.

This problem can be solved using two pointers that are initially pointing to the head node. Let’s name the two pointers as `slow_ptr`

and `fast_ptr`

.

The steps of the algorithm are as follows:

- Initialize
`slow_ptr`

and`fast_ptr`

to the head node. - Continue performing the following steps until the
`fast_ptr`

or the next element of`fast_ptr`

reaches the end of the list:- Move the
`slow_ptr`

by one node. - Move the
`fast_ptr`

by two nodes.

- Move the

By the time `fast_ptr`

reaches the end of the list, `slow_ptr`

will be pointing to the middle node of the list.

- Time complexity:
`O(N)`

- Space complexity:
`O(1)`

public class Main{ static class Node{ int data; Node next; public Node(int data) { this.data = data; this.next = null; } } static class SLL{ Node head; public SLL() { this.head = null; } public void pushFront(int data){ Node node = new Node(data); node.next = head; head = node; } public void print(){ Node temp = head; while(temp != null) { System.out.print(temp.data + " -> "); temp = temp.next; } System.out.println("NULL"); } public void getMiddle(){ if(head == null) { System.out.println("Empty list. Cannot get the middle node"); return; } Node slowPtr = head; Node fastPtr = head; while(fastPtr != null && fastPtr.next != null){ slowPtr = slowPtr.next; fastPtr = fastPtr.next.next; } System.out.println("The middle element is - " + slowPtr.data); } } public static void main(String[] args) { SLL sll = new SLL(); sll.pushFront(5); sll.pushFront(4); sll.pushFront(3); sll.pushFront(2); System.out.println("Even number of nodes list:"); sll.print(); sll.getMiddle(); System.out.println("----"); System.out.println("Odd number of nodes list:"); sll.pushFront(1); sll.print(); sll.getMiddle(); } }

Mid of SLL in Java

RELATED TAGS

java

CONTRIBUTOR

Ravi

RELATED COURSES

View all Courses

Keep Exploring

Related Courses