Reverse one linked list without using pointers

Question

When I speak without using any pointers, I mean that we still use the "next" field to move around the list, but without changing them when the list is inverted.

From what I could understand, there seem to be ways:

• One way is to change the data in the nodes without changing the pointers themselves.
• The second way is to create a new linked list that is inverse to the original linked list.

I would appreciate it if someone could help me on how to move on to the first method. Other methods are also welcome.

Answer 1

This problem is not much different from any other reversal problem. One solution is to view the list and place each data item in the array. Then go to the list again, but start at the end of the array, and you will overwrite the list data with the values ​​from the array in the 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, recursion is also missing, as it acts as a helper array for storing your inverted list. Then a stupid solution would be to implement a random list access interface:

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

Returns the element n ^th in the list. Then you change the list using this interface, which allows you to access it as an array (of course, taking into account the time). Cancellation no longer takes O (n) time, but now O (n ² ).

---

If the recursion is OK, then to satisfy the requirement "without saving elements" you need to recursively list, and then expand the list when you relax. This can be done by allowing another parameter of the recursive call to provide the pointer needed to go through the beginning of the list, since recursive calls are deployed from the end. This implementation does not use additional local variables for a recursive call, but only the variables represented 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 on the spirit of “without preserving elements” requirements when using recursion, then there is a more direct (but more hungry) space. Basically, a copy of an inverted linked list can be created with a recursive move. When the end of this is achieved, the list can again be gone by 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 2

Today at work, I continued to return to this issue, trying to figure it out. I found that your limitations are somewhat confusing, so "have you tried magic?" comment. In the end, I got over the block ...

This can help visualize the problem. Let's start with the ideas in the Julio Moreno code, which are somewhat simplified: go through the list and swap each node with tail data.

 ABCDE EBCDA EACDB EABDC EABCD EDBCA EDACB EDABC EDCBA 

(At work, I came to the conclusion that the process will not work, but now I have more time, I see that it is). If we then examine its function in more detail, we will see that, in addition to this, it also works recursively. I do not want to visualize the recursive function called from the for loop. This process is clearly not going to win prizes for efficiency.

So, let's see what we can do if we don’t want to limit ourselves to not changing the positions of the node:

 ABCDE BCDEA CDEBA DECBA EDCBA 

Here we take the tail of node E and remember it. Now take node A and insert it after E, then B and insert it again after E, but before A, going through the whole list, pasting right after E until E becomes the first node (head) of the list. It works, but we are not allowed to do this.

Let's take it one step further and pretend it is a doubly linked list, we support two pointers: one at the beginning of the list and one at the end, and we exchange the data of both, and then increase one and decrement the other, respectively.

 ABCDE EBCDA EDCBA 

Done already!

So how can we do this with a singly linked list? What do we need to know? How can we step back while moving forward?

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

 ABCDEFGH 

And replace them:

 HBCDEFGA 

and then, if we remember both nodes that we exchanged for data , we can start with B and step until node → points to node, now containing data A.

 BCDEFG 

and replace them:

 GCDEFB FDEC ED 

However, I’m still embarrassed with the idea of ​​repeatedly navigating through the list - even if the range of steps is reduced at each iteration of the process. What if we had a LIFO (last in the first) or a stack, as it was known?

 ABCDEFGH BCDEFGH ... A CDEFGH ... B DEFGH ... C EFGH ... D FGH ... E GH ... F H ... G...F...E...D...C...B...A 

But this is an auxiliary data warehouse, and we do not allow this, but it is not too difficult to understand how LIFO can be implemented using recursive function calls and a linked list. So, how could we move back and forth with a recursive function call and linked list? Do we need an additional parameter? When we get to the end of the list, we still need to know how it starts.

 ABCDEFGH A,B ^ return 0 A,C ^ return 0 A,D ^ return 0 A,E ^ swap DE done, return 0 A,F ^ swap CF return D A,G ^ swap BG return C A,H ^ swap AH return B 

I have not tested this to prove it, so this may be wrong. I'll check it now and publish the code if necessary. I hope I do not have to edit this post to say that it does not work; -)

EDIT: can confirm that 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 only called as many times as there are items in the list.

Answer 3

Something like this will work, the first function does not actually switch (sorry for the confusing name), it is very similar to the insertion algorithm, it takes the last element of the list and inserts it into the "current" position. I have serious doubts about the effectiveness 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); } 

Answer 4

@ames Morris - very nicely explained. But well, what's the difference between your and my code ...

Uses 2 pointers with 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 5

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

Once you have implemented the stack, it handles most of the handling problems well.

Of course you use more space, which means it is out of place.

Answer 6

  //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; }