top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How to find the median of simple linked list and add a node after it?

+2 votes
360 views

How to find the median of simple linked list and add a node after it? C program would be helpful?

posted Dec 29, 2015 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+1 vote

This pseudo-code holds for a Single Linked list:
1. init two pointers(p1,p2) at head of the linked list
2. p2 traverses twice as fast as p1
3. For each iteration p1=p1.next and p2=p2.next.next;
4. if p2==null or p2.next=null return middle element = p1
5. Repeat Step 2
6. return p1
This pseudo-code holds for adding node after getting p1 as median
if(p1==null)enter code here
add node at p1
else
{
store next node of p1 in temp
add new node at p1.next
add temp at p1.next.next
}
Complexity : O(n)+1

answer Dec 29, 2015 by Rajan Paswan
Similar Questions
+3 votes

How to delete the node that given as argument in single linked list?
Is there any system call to get prev pointer ?

Note: Here the goal is to delete the address not the node's value

...