I have a real world problem where I have a list of nodes. Each ones contains a name and the name of the node before it in order. I am trying to devise an algorithm to sort these in order. The problem is that any two random nodes will not tell me anything about their order unless they happen to lie next to each other, so I can't use a traditional sorting algorithm.
When I try to work through ideas everything basically comes down to "grab" the node at the start and then place it after the correct node" then repeat with the next node at start of the list. The problem is this has worse case running time of $O(n^2)$ complexity if the items are reversed. Any ideas of how to efficiently solve a problem like this?