- Among all cities not in the tour, choose the one that is
*farthest*
from any city already in the tour.
- Insert it into the tour in the position
where it causes the smallest increases in the tour distance.

You will have to store all of the unused cities in an
appropriate data structure, until they get inserted into the tour.
If your code takes a long time, you algorithm probably
performs approximately N^{3} steps.
If you're careful and clever, this can be improved to
N^{2} steps.
**Node interchange local search.**
Run the original greedy heuristic (or any other heuristic).
Then repeat the following:

- Choose a pair of cities.
- Swap the two cities in if this improves the tour.
For example if the original greedy heuristic returns 1-5-6-2-3-4-1,
you might consider swapping 5 and 3 to get the tour
1-3-6-2-5-4-1.

Writing a function to swap two nodes in a linked list provides
great practice with coding linked lists.
Be careful, it can be a little trickier that you might first
expect (e.g., make sure your code handles the case when the 2 cities
occur consecutively in the original tour).
**Edge exchange local search.**
Run the original greedy heuristic (or any other heuristic).
Then repeat the
following:

- Choose a pair of edges in the tour, say 1-2 and 3-4.
- Replace them with 1-3 and 2-4 if this improves the tour.

This requires some care, as you will have to reverse the orientation
of the links in the original tour between nodes 3 and 2 so that
your data structure remains a circular linked list.
After performing this heuristic, there will be no crossing
edges in the tour, although it need not be optimal.