Insertion sort on linked list

If you want a simpler algorithm that needs only O(1) space, you can also consider using insertion sort to sort the linked lists. While insertion sort is easier to implement, it runs in O(n²) time in the worst case (though it also has O(n) best-case behavior), so it's probably not a good choice unless you specifically want to avoid merge sort.
The idea behind the insertion sort algorithm is as follows:

1. Initialize an empty linked list holding the result.
2. For each of the three linked lists:
   1. While that linked list isn't empty:
      1. Scan across the result list to find the location where the first element of this linked list belongs.
      2. Insert the element at that location.