Communiquez avec les autres et partagez vos connaissances professionnelles

Inscrivez-vous ou connectez-vous pour rejoindre votre communauté professionnelle.

Suivre

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

user-image
Question ajoutée par lakshmipathi danti , Project leader
Date de publication: 2016/04/22
Christo Kotze
par 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.

Utilisateur supprimé
par Utilisateur supprimé

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
par 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