Fastest algorithm for a 'circular linked list builder'

Question

I have two questions:

1) What is the fastest algorithm to put this list in a "connecting" order?
2) Is this an existing problem/algorithm, and what name does it have?

The nodes are always connected in a circular fashion, so my starting ID does not matter.

Given this list:

id node1 node2
A  4     9
B  6     1
C  1     3
D  3    10
E  7     2
F  4     2
G  9     8
H 10     5
I  7     5
J  6     8

node1 & node2 are not in a specific order so id A can be 4 - 9 as well as 9 - 4.

The output should be this (it doesn't matter if it starts with A, as long as the output is a chain).

node ids: 4 - 9 - 8 - 6 - 1 - 3 - 10 - 5 - 7 - 2 - 4
ids:        A   G   J   B   C   D    H   I   E   F

(I am writing my code in C#. But pseudo code in any language will do)

Answer 1

You can do it the following way:

static IEnumerable<Edge<T>> OrderEdges<T>(this IEnumerable<Edge<T>> edges)
    where T : IEquatable<T>
{
    Debug.Assert(edges.Any());
    var map = new Dictionary<T, Edge<T>>();

    foreach (var e in edges)
    {
        if (map.ContainsKey(e.Node1))
        {
            Debug.Assert(!map.ContainsKey(e.Node2));
            map.Add(e.Node2, e);
        }
        else
        {
            map.Add(e.Node1, e);
        }
    }

    var current = edges.First();
    var orderedEdges = new HashSet<Edge<T>>();

    while (true)
    {
        orderedEdges.Add(current);
        yield return current;

        if (orderedEdges.Count == map.Count)
            break;

        var next = map[current.Node2];
        current = orderedEdges.Contains(next) ? map[current.Node1] : next;
    }
}

Where the Edge<T> class is simply:

class Edge<T> where T: IEquatable<T>
{
    public T Node1 { get; }
    public T Node2 { get; }
    public string Name { get; }
    public Edge(string name, T node1, T node2)
    {
        Name = name;
        Node1 = node1;
        Node2 = node2;
    }

    public override string ToString() => Name;
}

If we run this little guy:

var edges = new List<Edge<int>>() {
    new Edge<int>("A", 4, 9), new Edge<int>("B", 6, 1),
    new Edge<int>("C", 1, 3), new Edge<int>("D", 3, 10),
    new Edge<int>("E", 7, 2), new Edge<int>("F", 4, 2),
    new Edge<int>("G", 9, 8), new Edge<int>("H", 10, 5),
    new Edge<int>("I", 7, 5), new Edge<int>("J", 6, 8) };

Console.WriteLine(string.Join(" -> ", edges.OrderEdges()));

We get the expected result:

A -> G -> J -> B -> C -> D -> H -> I -> E -> F

Do note that this solution presupposes that the input data is well formed.