Akamai Interview Question Quality Assurance Engineers
Country: India
Interview Type: In-Person
Using 2 pointers is considered one pass..you are surely using 2 pointers but traversing the list only once.
I would not consider using two pointers to be one pass. Advancing two pointers through a linked list is the same as traversing it twice.
I guess different people may mean different things. But advancing two pointers is similar work to looping twice. You access every node twice, and so I would call that two passes.
You can do any number of operation on node in a single pass. Doing two operations t->next & t->next->next, is not consider two passes, it is consider as one pass.
@tej: We can argue about definitions, but it'll take 2N linked list pointer accesses. That's all I meant.
The while loops runs only once... and in that both pointers are incremented, so its one pass.
nodeType *slow = head;
nodeType *fast = head;
while(fast != null)
{
fast = fast -> link;
(i%2 == 0)
{
slow = slow -> link;
}
}
This way slow points to middle at the end. When fast reaches null.
/**
* find mid point
* 2 pointers - one more 2 times faste
*/
public void findMidPoint()
{
if( head == null ){
return;
}
Node<AnyType> fast = head;
Node<AnyType> slow = head;
while(true){
if( fast == null || fast.next == null ){
System.out.println("mid point value is: " + slow.data );
break;
}
fast = fast.next.next;
slow = slow.next;
}
}
If you don't want to use 2 pointers.. you can use array to store all values like
while(! node->next)
{
a[i++] = node->deata;
node = node->next;
count++;
}
cout << "moddle one is " << a[count/2];
int middleOfList(node *head)
{
if(head == NULL || head->next == NULL)
return -1;
node *ptr1 = head;
node *ptr2 = head->next;
while( ptr2 && ptr2->next)
{
ptr1 = ptr1->next;
ptr2 = ptr2->next->next;
}
return ptr1->data;
}
One corner case, which one is the middle one if number of elements is even in linked list ?
Use two pointers. Increment one pointer one position at a time and the other pointer two positions at a time. When the fast pointer reaches the end, the slow pointer should be at the middle position.
- Sandy September 04, 2012