Pages

Thursday, December 25, 2008

Code to find the middle element in a singly linked list.

Programming language used: C/C++

node* FindMiddle(node *head, node** middle)
{
if(!head || !(*middle))
return;
node* slow = head;
node* fast = slow->next;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}

*middle = slow->next;
return slow;
}

7 comments:

@VELU said...

a very concised code - nice one !!

Harish said...

Is node** middle an input? what does that store?

Harish said...

Well... assuming head and middle points to the first node, i could see the algo working..
But i don't get a point here. Why do you store *middle=slow->next and return slow.
In the case of my example 1->2->3->4->5, *middle = 4, slow = 3.
return slow make sense, but *middle=slow->next.
With the case, 1 to 8, *middle=5 and slow=4.

Global Handler said...
This comment has been removed by the author.
Harish said...

dei... waiting for your reply...

@VELU said...

may be one has to consider head as dummy node pointing to first node ...

Global Handler said...

Hey that was the method provided in an interview, and was supposed to fill in the method for the case. Seeing what exactly is done with the pointers...
but my bad not removing that method head...so using the below and ignoring the middle shoudld solve...

if(!head || !(head->next))
and just return slow;

btw to answer your another question why **, it is just a pointer to pointer, pass by ptr remember.

Thanks!