Start networking and exchanging professional insights

Register now or log in to join your professional community.

Follow

How to find out the middle node in single linked list with one pass when number of nodes are not known?

user-image
Question added by lakshmipathi danti , Project leader
Date Posted: 2016/04/22
Christo Kotze
by Christo Kotze , Head of Primary , Creative British School

In a nut shell, you make use of 2 pointers. The first one gets updated with every iteration (item read in the linked list) and the second only gets updated with every second item.

When the first one reaches the end of the list, the second one will be on the middle item.

All in one single pass.

This link shows the pseudo code, as well as java and javascript implementations.

Hope that helps.

create another list and keep appending nodes to the new list as u traverse through the list and keep count, once you reach the end divide the count by 2 and upper the value and use it to access the new node.

Muhammad khan KHALID KHAN
by Muhammad khan KHALID KHAN , ELECTRICAL SUPERVISOR , ACC AL ARRAB CONTRATING COMPANY Ltd

Method 1: Traverse the whole linked list and count the no. of nodes. Now traverse the list again till count/2 and return the node at count/2. ..... @geeksforgeeks we can alsofind middle element by using recursion. see .... this is correct as we know that mid of two elements is 1st element and not second. ... System.out.println

More Questions Like This

Do you need help in adding the right keywords to your CV? Let our CV writing experts help you.