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