Interview Question

Software Engineer Interview Seattle, WA

To copy a linked list. Every node's prev points to the

  previous node, but the next points an arbitrary node.
Answer

Interview Answer

2 Answers

0

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).

Daniel on Jan 29, 2013
0

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;

Jake on Feb 5, 2013

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up