Linked list question

[electroRF]

Hi,
I ran into the following question that was asked in an interview and I really hope to be able to answer it correctly.

The question is not that clear - but i write it here word for word:

- Given a singly-linked list.
- there's a program in which the next node to be looked is in + or - K steps from the previous found Node.
- Write that program which finds the next node in the fastet run time.

I believe that the program receives the previous node that was found, and a number K (which can be positive or negative), and it needs to find the next Node which is K steps from the previous node.

I don't manage to find a solution which is less then O(K).

Do you have an idea?

Thank you very much.

 

[Pommie]

As it's singly linked then there is no way to go back a node and so for negative values of k you would have to start at the beginning of the list and work your way through. Or did I miss something?

IMHO, the way to get the fastest run time is to convert to a doubly linked list. If memory is a problem then Xor-linking might be possible.

Mike.

 

[electroRF]

Hi Mike,
Thanks a lot!

I got 2 questions please

1. to convert a singly-linked list to doubly-linked list, Can I add a 'previous' pointer to each node IN-PLACE?
or Must I create a new allocation for an entire doubly-linked list at the length of the original list?

2. By doing this, it'd still take me O(K) to find the K (+/-) node, right?
in the question, they said "the fastest run time" so I suppose it can be done in less than O(K).

 

[Pommie]

1 To make it doubly linked you have to add a previous pointer which would require creating a new list (or doing lots of shuffling of the original). Alternatively Xor-Linking could be used to convert the list in place.

2. I don't see how it could be quicker unless extreme measures are taken such as having binary pointer so you can jump 128, 64, ... 1 nodes in a single bound. This would make k=48 a two jump solution which is very fast but would require a large amount of memory.

Mike.

 

[NorthGuy]

I think if you want to go back K nodes in a single-linked list, the best way is to go from the beginning and count nodes until you get your node. Suppose it is number N. Then you subtract K from the count and go from the beginning (N-K) steps.

You can optimise the second pass if you build a set of interim pointers during the first pass, but moving through the list is very fast, so it will only make things slower.

If you get such question on the interview, first tell them that for going backwards, the single-linked list is a poor choice.