0

I have to write a function to reverse a double linked list, so that the tail becomes the head.

For example, the elements before: {(1,1), (1,2), (2,2), (2,3)}

after: {(2,3), (2,2), (1,2), (1,1)}

Here's the structure:

  struct snake {
    unsigned int i;
    unsigned int j;
    struct snake *next;
    struct snake *prev;
  };

This is the function prototipe I must use:

void snake_reverse(struct snake **s);

I tried something like this and several other attempts

void snake_reverse(struct snake **s) {
struct snake *last, *tmp = NULL;

last = *s;

while (last !=  NULL)
 {
   tmp = last->prev;
   last->prev = last->next;
   last->next = tmp;
   last = last->prev;
 }

 if(tmp != NULL )
    *s = tmp->prev;
}

Also tried this:

while (last !=  NULL)
 {
   tmp = last->next;
   last->next = last->prev;
   last->prev = tmp;
   last = tmp;
 }

 if(tmp != NULL )
    *s = tmp;

but he doesn't work. I'm almost sure I'm not wrong. The first ->prev of the list is NULL, the last ->next of the list is NULL.

I get no errors or crash, but the task of the function is to invert the direction of the snake by reversing all elements and changing the head of the list. Can you say what's wrong here?

EDIT: The problem was in another module of the program not made by me.

Anyway the best solution is that of kmkaplan. Thanks everybody

Improve this question
4
  • When you describe a problem, you cannot just say "it does not work"; it is better if you are more precise: here is what I did, the expected output is X but I have Y (alternatively: there is a crash with error message Z). Maybe the actual bug lies in the way you test your function. Commented Feb 15, 2017 at 18:04
  • See also last = last->prev: would it make sense to have last = tmp instead? Commented Feb 15, 2017 at 18:06
  • @coredump sorry if I can't be more specific but this function is used as a module in a program and I can't control the rest of the program. Anyway I get no errors or crash, but the task of the functions is to invert the direction of the snake by reversing all elements and changing the head of the list. last->prev has the address of last->next cause we switched them. tmp has last->prev. So they are different Commented Feb 15, 2017 at 18:18
  • You should make an exception where next or prev are the end markers, and set head and tail. But can you side-step the problem by setting a flag to tell you in which direction the list is to be parsed? Head to tail, or tail to head. To reverse direction, you would invert the flag. Job done. Commented Feb 15, 2017 at 18:28

3 Answers 3

Reset to default
1

You have to set *s to the new head of the list. That is the old tail of the list, the last element you process.

void snake_reverse(struct snake **s) {
    struct snake *last, *tmp = NULL;
    last = *s;
    while (last !=  NULL) {
        *s = last
        tmp = last->prev;
        last->prev = last->next;
        last->next = tmp;
        last = last->prev;
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks, this really reverse the elements ( i checked the address of the elements and they are reversed) but the snake in the game still gets stuck when it calls this function. So i think it's not my fault and the problem is in another function
The problem was in another module of the program, not made by me. Anyway this seems the best solution and worked
0

I am not sure but I think that the last line of code in your while loop is wrong. As I understand the last variable is the tail of the snake. That means that last->next = null. In the second line of code in your while you make the previous of last null and in the last line of code in the while the last becomes 0. I think that changing your last line of code in the while loop will change this.

last = last->next
Improve this answer

1 Comment

I tried but he doesn't work. Teorically in the last line of the while loop last->prev has the address of last->next, so it's right to use last->prev to move to next element of the list
0

You're never setting the new head of the list since tmp is always NULL after the while loop. Try this;

void snake_reverse(struct snake **s) {
  struct snake *last, *newHead, *tmp = NULL;

  last = *s;

  while (last !=  NULL)
  {
     tmp = last->prev;
     if (tmp!=NULL)
       newHead = tmp;
     last->prev = last->next;
     last->next = tmp;
     last = last->prev;
  }

  *s = newHead;
}
Improve this answer

1 Comment

Thank you for the answer but nothing to do, the snake still gets stuck in the game when i call this function. Then i think something is wrong. For a little debug these are the address of the elements: Before the loop *s = 16595408 *s->next = 16595360 *s->prev = 0 After the *s = newHead *s = 16595408 *s->next = 0 *s->prev = 1659536

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.