View All num of num See all Photos Amazon.com www.amazon.com Engaged Employer Overview Reviews Salaries Interviews Jobs Photos Benefits 5.3k Reviews 12k Salaries 6.5k Interviews 7.4k Jobs Follow Add Interview Follow Add Interview Interview Question Software Engineer Interview Seattle, WA Amazon.com To copy a linked list. Every node's prev points to the previous node, but the next points an arbitrary node. Tags: See more , See less 8 Answer Add Tags 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 Interviews > Software Engineer > Amazon.com Add Answers or Comments To comment on this, Sign In or Sign Up.