Is there a O(nlog(n)) algorithm for inverting a simply linked list?

Question

In comments to this answer an idea is brought up that inverting a simply linked list could only be done in O(nlog(n)), not O(n) time.

This is definitely wrong – an O(n) inversion is not a problem - just traverse the list and change pointers as you go. Three temporary pointers are required - that's constant extra memory.

I understand completely that O(nlog(n)) is worse (slower) than O(n).

But out of curiosity - what could be a O(nlog(n)) algorithm for inverting a simply linked list? An algorithm with constant extra memory is preferable.

Answer 1

I think you're confused. You're saying O(n log(n)) which is in fact worse than O(n). Do you perhaps mean O(log n)? If so, the answer is no. You can't invert a linked list in O(log n). O(n) is trivial (and the obvious solution). O(n log(n)) doesn't make a lot of sense.

Edit: Ok, so you do mean O(n log(n)). Then the answer is yes. How? Easy. You sort the list:

1. Count the length of the list. Cost: O(n);
2. Create an array of that same size;
3. Copy the elements of the linked list into the array in random order, putting the original order as part of the element. For example: [A,B,C] -> [(B,2),(C,3),(A,1)]. Cost: O(n);
4. Sort the array using an efficient sort (eg quick sort) in inverted original order eg [(C,3),(B,2),(A,1)]. Cost: O(n log(n));
5. Create a linked list from the reversed array. Cost: O(n).

Total Cost: O(n log(n))

Despite all the intermediate steps, the sort is the most expensive operation. The O(n) other steps are constant (meaning the number of steps is not a factor of n) so the total cost is O(n log(n)).

Edit 2: I originally didn't put the list items in random order but realized that you could argue that an efficient sort on an already sorted list was less than O(n log(n)) even if you were reversing it. Now I'm not completely convinced that that's the case but the above revision removes that potential criticism.

And yes, this is a pathological question (and answer). Of course you can do it in O(n).

Answer 2

Well...

You could use a recursion that accepts a linked list and inverts it, by calling itself with two halves of the linked list, where if the input is just two nodes, it inverts them.

This is highly inefficient but I believe it's O(nlog(n))...

Something like the following in pseudo code (assuming you have a len function that returns the length of a list in O(n) and a sub_list(list, start_id, end_id) function that returns a subset of list starting at start_id and ending at end_id in O(N)):

function invert(list)

    if len(list) == 1 return list

    if len(list) == 2:
        new_list = list.next
        new_list.next = list
        return new_list

    middle_of_list = len(list) / 2  <-- integer division

    first_half = invert ( sub_list(list, 1, middle_of_list) )
    second_half = invert ( sub_list(list, middle_of_list+2, len(list) )

    first_half.next = second_half

    return first_half

Answer 3

Every O(n) algorithm is also O(n log n), so the answer is yes.

Answer 4

Stupid idea, but O(n log n) and not O(n)

• Assign each item of a list an unique ID. The id of each successor should be greater than the id of the item (O(n))
• Sort the items by ascending order using the id as key using any comparison based sorting algorithm (O(n log n))
• Build up a new list using the order given by sorting the items (O(n))

Answer 5

If you are pedantic then this algorithm is O(n log n), because the pointers are of size at least log n and must be assigned n times.

But in reality machines have a fixed word size, so this isn't usually taken into account.

Answer 6

If the question is actually for a Ω(nlgn) algorithm, perhaps this overly complicated algorithm will do?

• build a balanced tree structure from the linked list
• each leaf contains both original value from the linked list and an index number of the value in the linked list; use the index as the tree key
• traverse the tree to report all leafs in reverse order to the original index
• create a new linked list from the matching values