A singly linked list is a list in which a pointer p has two values: key(p) and n

Question

A singly linked list is a list in which a pointer p has two values: key(p) and next(p) (thus there is no previous(p)). A pass on a singly linked list starts with the assignment of a finite number of pointers to the start of the list, and then moving the pointers further the list (there are no restriction on how much the pointers can go forward but they can not go backward).

Given a 2n size Linked list with s pointing to the head of the list, design a single pass algorithm that returns the n’th (or middle) item in the list. Use as few pointers as you can.

If you find it hard to do it in one pass, give a two pass algorithm that finds n number in the list.

No code, just algorithm. Please analyze complexity.

Explanation / Answer

It's a single pass algorithm. Nothing much logic in this. You'll start at a point to where head is pointing to. That would is you start with a pointer assume temp pointing to the first node. Now temp->key points to the value temp is hollding. And temp->next will point to the next node i.e., to the second node. So, now if you want to move to the second pointer I.e., if you want temp to point to second node just assign the address in temp->next to temp. So, the step

temp = temp->next;

will make you traverse further.

Initially you made temp point to the first node. Now if you execute the above said step for n-1 times, you'll simply traverse to the nth node. Therefore the loop should run like this.

for(int i=0; i<n; i++)

temp=temp->next;

will make you access the nth node in the list. If you want to return this node value, you can simply write the statement return temp; will do the needful.   

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.