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

 //Reversal of linked list without using pointers.
void reverseList(ListNode* head) {
    if(head == NULL || head->next == NULL)
        return head;
    reverseList(head->next);
    //save the current value
    int val = head->val;
    ListNode *temp = head;
    // shift all the values to the left
    while(temp->next != NULL)
    {
        temp->val = temp->next->val;
        temp = temp->next;
    }
    // assign the save value at the end of the list
    temp->val = val;
    return;
}

Answer 2

Implement a stack and use it to reverse the linked list. Stack is a First In Last Out data structure (FILO). Push the contents of the linked list onto the stack in the first iteration and then pop them back into the list during the second iteration.

Once you have a stack implemented, it serves most of the reversal problem well.

Off course, you use more space, meaning its not in-place.

Answer 3

@ames Morris -- very nicely explained. But well what would be the difference between your and mine code ...

Uses 2 pointers at max ...

Node* reverseLL (Node *curr, Node *prev)
{
  Node *nxt = NULL;
  if (curr)
  {
    nxt = curr->next;
    curr->next = prev;
    curr = reverseLL (nxt, curr);
  }
  else
    return prev;
}

void reverseList (Node **head)
{
  Node *curr = *head;
  Node *prev = NULL;
  curr = reverseLL (curr, prev);
  *head = curr;
}

Answer 4

This problem is not much different from any other reversal problem. One solution is to walk the list, and place each data item into an array. Then, walk the list again, but start at the end of the array, and you overwrite the list data with the values from the array in reverse order.

for (n in list) arr[i++] = n->data
for (n in list) n->data = arr[--i]

If you are not allowed to store anything, then recursion is also out, since it acts as an auxiliary array to store your reversed list. Then a silly solution would be to implement a random access interface to the list:

Node * nth_list_item (Node *list, int n);

Which returns the n^th item of the list. Then, you reverse the list with this interface that lets access it like an array (with a time penalty of course). The reversal no longer takes O(n) time, but is now O(n²).

---

If recursion is okay, then to satisfy the spirit of the "without storing elements" requirement, you need to walk the list recursively, and then reverse the list as you unwind. This can be accomplished by allowing another parameter to the recursive call to provide the pointer needed to walk through the beginning the list as the recursive calls are unwinding from the end. This implementation uses no extra local variables per recursive call, only the variables provided in the parameters.

void swap_left (node *a, node *b, int tmp) {
    a->data = b->data;
    b->data = tmp;
}

void reverse_recursively (node *cur, node **tail) {
    if (cur) {
        reverse_recursively(cur->next, tail);
        if (*tail) {
            swap_left(cur, *tail, cur->data);
            if (cur != *tail) *tail = (*tail)->next;
            if (cur == *tail) *tail = 0;
        }
    }
}

void reverse (node *list) {
    reverse_recursively(list, &list);
}

---

If we are allowed to encroach upon the spirit of the "without storing elements" requirement when using recursion, then there is a more straight forward (but more space hungry) solution. Basically, a copy of the reversed linked list can be created while recursively traversing it. When the end of it is reached, the list can be traversed again, copying in the elements from the reversed copy.

#define make_node(n, d) (node){ n, d }

void reverse_recursively (node *list, node *cur, node copy) {
    if (!cur) {
        for (cur = © cur; cur = cur->next, list = list->next) {
            list->data = cur->data;
        }
        return;
    }
    reverse_recursively(list, cur->next, make_node(&copy, cur->data));
}

void reverse (node *list) {
    if (list == 0) return;
    reverse_recursively(list, list->next, make_node(0, list->data));
}

Answer 5

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.

Answer 6

Something like this would work, the first function doesn't actually switches (sorry for the confusing name), it works much like an insertion algorithm, it takes the list's last element and inserts it into "current" position. I have serious doubts about the efficiency of this algorithm:

    typedef struct node node;
    struct node {
        node *next;
        void *value;
    };
    typedef node linked_list;

    node *switch_with_end(node *c)
    {
        if (c->next) {
            node *t = switch_with_end(c->next);
            void *temp = t->value;
            t->value = c->value;
            c->value = temp;
        }
        return c;
    }

    void reverse_list(linked_list *l)
    {
        node *c;
        for (c = l; c->next; c = c->next)
            switch_with_end(c);
    }