this solution will be shorter if C# has built-in priority queue library.....

Inspired by @StefanPochmann approach, basically it's his idea in C# verison.

It works well and can handle test cases that contains invalid itineraries. Like [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"]] .

Time: Assume we have N itineraries, each itinerary has two string=> 2N strings.

- we build hashtable for all itineraries. O(N) time
- we sort values string for each key. O(N* NlogN) time
- we backtracking to find the next city we want, until all city has added. Since we use hashtable in the searching so it's O(N).

4.Convert out result linkedlist to a list, not sure if it's O(N) or O(1) in C# but can never greater than O(N).

Adding together it’s O(N*logN) time.

Space: we use a hash table and a stack, so it's O(2N)=>O(N) space

```
public IList<string> FindItinerary(string[,] tickets)
{
LinkedList<string> res= new LinkedList<string>();
//invalid input
if (tickets == null || tickets.Length == 0) return res.ToList();
//Build a hashtable/dict for route.
//key is the source city, value are all the destination city from source city.
var routeDict = new Dictionary<string, List<string>>();
int count = tickets.GetLength(0); //tickets number
for (int i = 0; i < count; i++)
{
var source = tickets[i, 0];
var dest = tickets[i, 1];
if(!routeDict.ContainsKey(source))
routeDict.Add(source, new List<string>());
routeDict[source].Add(dest);
}
//keep asce order
foreach (var list in routeDict.Values) list.Sort();
//need a stack as like a backtracking route from final.
Stack<string> stack = new Stack<string>();
stack.Push("JFK"); //Add start city
while (stack.Any())
{
while (routeDict.ContainsKey(stack.Peek()) && routeDict[stack.Peek()].Any())
{
var next = routeDict[stack.Peek()].First(); //the next city from the source city in lexical order
routeDict[stack.Peek()].RemoveAt(0); //remove the next city from the hash table.(since List<T> doesn't has Poll/Pop/Dequeue)
stack.Push(next); //push next city into the stack
}
res.AddFirst(stack.Pop()); //Pop all the city from stack, Add them in the head of res.
}
return res.ToList();
}
```