c - 反向双链表

Question

我必须编写一个函数来反转双链表，使尾部变成头部。

例如前面的元素: {(1,1), (1,2), (2,2), (2,3)}

之后: {(2,3), (2,2), (1,2), (1,1)}

结构如下:

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

这是我必须使用的函数原型(prototype):

void snake_reverse(struct snake **s);

我尝试了类似的方法以及其他一些尝试

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

也尝试过这个:

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

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

但他不工作。我几乎可以肯定我没有错。 列表的第一个 ->prev 为 NULL，列表的最后一个 ->next 为 NULL。

我没有遇到错误或崩溃，但该函数的任务是通过反转所有元素并更改列表头来反转蛇的方向。 你能说一下这里出了什么问题吗？

编辑:问题出在不是我制作的程序的另一个模块中。

无论如何，最好的解决方案是 kmkaplan。谢谢大家

Answer 1

您必须将*s 设置为列表的新头。这是列表的旧尾部，即您处理的最后一个元素。

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