programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Linked List with a random pointer

Prasanna Raman
Ranch Hand
Posts: 410
I came across this question in this book:

A "postings list" has a data field, a field for the next pointer and a jump field - the jump field points to any other node. The last node in the postings list has next set to null; all other nodes have non-null next and jump fields.
Implement a function that a postings list as input and returns a copy of the list, in O(n) time and O(1) storage beyond that required for the nodes in the copy. You may modify the original list but must return it to its original state before returning.

I was able to find a solution, but not one that runs in O(n) time. I did try to work out the steps on a piece of paper as many of you here recommend, but the solution they have doesn't seem intuitive to me. I do understand how the solution works but I don't know if I would have ever solved it.

So, I just wanted to ask around and see how some of the experienced programmers here would have approached this problem. Is there a way to approach these kind of questions? Or does it just mean that I have work to do?

fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
Off the top of my head, I'd say you have to iterate through the list once to find how many nodes there are O(n).

Then, generate a random number from 1 to n-1 O(1);

then iterate through the list to that node, skipping over/not counting the current node who's value you are trying to set. O(n).

Once you have that node, you can point to it.

Time = O(n) + O(1) + O(n) = 2 * O(n) + O(1)

Since you drop the lowest order term (O(1)), and the coefficients, that leaves O(n).

I'm not sure this works...but I don't see any obvious flaws...

Prasanna Raman
Ranch Hand
Posts: 410
I've made a small edit to the question.

Prasanna Raman
Ranch Hand
Posts: 410
Fred, does your solution create a copy of the original list?

fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
no, but it could be amended to do it.

Martin Vajsar
Sheriff
Posts: 3752
62
Fred, I don't see how to amend your idea to copy the list. I especially don't see any place for the random generator, as I understand that the task is to copy the topology of the list exactly. And I must admit I still don't see a solution that would meet both speed and storage constraints. It's easy to meet one or the other, but not both.

fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
Maybe I don't understand the problem then. i'll try to circle back if I have time.

Matthew Brown
Bartender
Posts: 4568
9
I've seen one like this before. I think the trick is that you're allowed to temporarily change the links in the existing list, as long as you reinstate them by the time you finish copying.

So I think you can do it in three passes:

- First pass: copy each node, but also update the "next" pointer of the original nodes to point to the copy, and the "next" pointer of the new nodes points to the next original node. You've effectively interleaved the new nodes with the old ones in the linked list.

- Second pass: for each new node, work out where the jump node needs to point to, and set it. This is possible because of the interleaving.

- Third pass: set the correct values for the "next" pointers (which involves reinstating the original values for the original nodes).

Does that sound like the solution you've been given?

Prasanna Raman
Ranch Hand
Posts: 410
Yes, Matthew

 It is sorta covered in the JavaRanch Style Guide.