Algorithm to create a linked list from a set of nodes

Question

Hi, I am looking for an algorithm to create a linked list from a set of nodes. For example, let's assume a node is an airline ticket from a source point to destination. (e.g., Chicago to Detroit) and there are several airline tickets. Assuming all these airline tickets are jumbled, what is the best way to determine the entire journey path. If there are 5 airline tickets like Chicago->Detroit, Denver->Chicago, Detroit->DC, DC->New York, San Jose->Denver, the algorithm should be able to come up with the correct start to end path.

San Jose -> Denver -> Chicago -> Detroit -> DC -> New York

Answer 1

If you are guaranteed that the nodes will form a single path (ie, maximum indegree is 1, maximum outdegree is 1, exactly one node has indegree 0, exactly one node has outdegree 0), then you could do the following:

• Construct two hashes: in_cities and out_cities
• For every node A -> B, add it to in_cities with key A and out_cities with key B
• Pick a node arbitrarily, call it S
• Have curr point to S. While the source city of curr is in out_cities, insert the corresponding node in the beginning of the path. Update curr to point to this node.
• Have curr point to S. While the destination city of curr is in in_cities, add the corresponding node to the end of the path. Update curr to point to this node.

Now you are done, in linear time with respect to the total number of cities.

Answer 2

This is not a linked-list question; it's a graph theory question.

A graph is mathematically defined as a set of vertices, and a set of edges, which are pairs of vertices that are defined as "adjacent". The edges can also be defined to be directed (such is the case in your scenario).

A path in a graph is a sequence of vertices such that there is an edge from each of the vertices to the next vertex in the sequence.

Adjacency relationship are commonly represented in one of two ways: adjacency matrix (a simple 2D array), or an adjacency list (which uses a linked list), but problems and solutions can be defined regardless of representation (though it does have an effect on complexity).

The shortest path problem, for example, assigns weights to the edges, and require a path between two nodes whose total weight is minimized. The classic solution taught in computer science course is Dijkstra's algorithm.

Most good algorithm books have a chapter on elementary graph theory.

---

Having said all that, there is a special kind of graph that is called a path graph, which may be what your input graph is (it can only be confirmed once all the assumptions of the problems are made explicit). If your input graph is of this simple type, then an easy solution to your problem exists (see danben's answer).

I will present the same algorithm in pseudocode form:

LET pred BE a MAP City=>City // "predecessor"
LET succ BE a MAP City=>City // "successor"

// build pred and succ
FOR EACH Ticket(City A, City B) DO
   pred[B] = A
   succ[A] = B

// find the starting city, i.e. one that doesn't have a pred
LET C BE any City
WHILE pred[C] != NULL
  C = pred[C]

// keep going until you reach the end
WHILE C != NULL
  PRINT C
  C = succ[C]

With a good MAP implementation, this is O(N) where N is the number of tickets.