To copy a linked list. Every node's prev points to the previous node, but the next points an arbitrary node.

Question

Daniel · Accepted Answer

Since the nodes have both "next" and "prev" pointers, this sounds like a doubly-linked list. Ask if that is the case and whether the list's "tail" pointer points to the correct node, then just use the tail and prev pointers to iterate through the list backwards, prepending each element to your new list.

If the original list doesn't have a tail pointer, or if it doesn't point to the correct node, then it *may* not be possible. To be possible, you must know the length of the list. If you DO know the length of the list, you can try iterating through the "next" pointers until you find a node with a "prev" trail the same length as the list. If you find one, it'll be the tail node and you can do as above.

Note, however, that the sequence of "next" pointers may form a cycle without ever pointing to the true tail. You can ask if this is a possibility -- if so, you'd need to check for cycles as you iterate through the "next" pointers (you can use the tortoise-and-the-hare algorithm within the same while loop).

Jake · Answer

Insert a copy of each node after the node it's copying, so the list looks like this:

Node1.next -> Node1cpy.next -> Node2.next->Node2cpy.next,

Then basically you make two more passes, one two nodes at a time looking like this:

Node1.next->arbitrary = Node1.arbitrary->next; 

Then split the lists:

Node1.next = Node1.next->next;
Node1Cpy.next = Node1Cpy.next->next;

Amazon

Amazon Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches