Reversing a singly linked list without using any pointers

Question

When I say without using any pointers, I mean we still use the 'next' pointer field to traverse through the list, but not changing them when reversing a linked list.

From what I could figure out there seem to be ways to this:

• One way is to reverse the data in the nodes without changing the pointers themselves.
• The second would be to create a new linked list which is a reverse of the original linked list.

I would be grateful if anyone could help me on how to proceed with the first method. Other methods are also welcomed.

Answer 1

Today at work I kept coming back to this question trying to make sense of it. I found your restrictions somewhat baffling, hence the 'have you tried magic?' comment. Eventually I got over the block...

It might help to visualize the problem. Let's start with the ideas in Julio Moreno's code, somewhat simplified: step through the list and swap each node data with the tail data.

A B C D E
E B C D A
E A C D B
E A B D C
E A B C D

E D B C A
E D A C B
E D A B C

E D C B A

(At work I concluded the process wouldn't work out, but now I have more time I can see it does). If we then take a closer look at his function we can see that on top of this, it also works recursively. I am not keen to visualize a recursive function called from a for loop. This process is clearly not going to win any prizes for efficiency.

So then let's look at what we could do if we didn't want to restrict ourselves to not modifying the node positions:

A B C D E
  B C D E A
    C D E B A
      D E C B A
        E D C B A

Here we take tail node E, and remember it. We now take node A and insert it after E, then B and insert it again after E but before A, stepping through the entire list inserting immediately after E until E is the first node (head) of the list. It works, but we're not allowed to do it.

Let's take the pretense one step further and pretend it's a doubly linked list, we maintain two pointers, one at the start of the list, and one at the end, and we swap the data of both and then increment the one and decrement the other, respectively.

A B C D E
E B C D A
E D C B A

Done already!

So how could we do that with a single-linked list? What do we need to know? How can we step backwards while simultaneously stepping forward?

Let's start with how we could get the last node by stepping through the entire list.

A B C D E F G H

And swap them:

H B C D E F G A

and then if we remember both the nodes we swapped the data of, we can start at B and step along until node->next points to the node now holding data A.

B C D E F G

and swap them:

G C D E F B
  F D E C
    E D 

However I'm still uncomfortable with the idea of repeatedly stepping through the list - even if the range of the stepping shrinks on each iteration of the process. What if we had a LIFO (last-in-first-out) or stack as it's otherwise known?

A B C D E F G H
  B C D E F G H ... A
    C D E F G H ... B
      D E F G H ... C
        E F G H ... D
          F G H ... E
            G H ... F
              H ... G...F...E...D...C...B...A

But that's auxiliary data storage and we're not allowed that, but it's not too difficult to see how a LIFO could be implemented with recursive function calls and a linked list. So how could we step forwards and backwards with a recursive function call and a linked list? Don't we need an extra parameter? When we get to the end of the list, we still need to know how it begins.

A B C D E F G H
A,B             ^ return 0
  A,C           ^ return 0
    A,D         ^ return 0
      A,E       ^ swap D E done, return 0
        A,F     ^ swap C F return D
          A,G   ^ swap B G return C
            A,H ^ swap A H return B

I've not actually tested this yet to prove it so it could be wrong. I'll go test it now and if requested may post the code. Hopefully I won't have to edit this post to say it doesn't work ;-)

EDIT: Can confirm it works.

static lnode* list_private_reverse(lnode* list, lnode* node)
{
    lnode* next = node->next;

    if (next)
    {
        lnode* swap = list_private_reverse(list, next);

        if (swap)
        {
            int c = swap->c;

            swap->c = node->c;
            node->c = c;

            if (swap->next == node || swap->next->next == node)
                return 0;

            return swap->next;
        }
        return 0;
    }
    else
    {
        int c = node->c;
        node->c = list->c;
        list->c = c;
    }

    return list->next;
}

lnode* list_reverse(lnode* list)
{
    list_private_reverse(list, list);
    return list;
}

list_private_reverse is called only as many times as there are elements in the list.