This pseudo-code holds for a Double Linked list:
1. init two pointers one at the start of the list(p1) and the other at the end (p2)
2. if p1=null or p2==null return NONE
3. At each iteration, visit node p1.next and p2.previous
4. if p1.next==p2.previous !=p1 || p2 then middle is obtained for an odd number of nodes. Return result
5. if p1.next==p2.previous=p1|| p2 then middle is for an even number of nodes. Return result(either p1 or p2)
6. Repeat 2
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
Complexity : O(n)
0 comments:
Post a Comment