反向双向链表

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

这是我必须使用的函数原型：

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为空，列表的最后一个->next为空。

我没有收到错误或崩溃，但函数的任务是通过颠倒所有元素并改变列表的头部来颠倒蛇的方向。你能说出这里出了什么问题吗？

编辑:问题出在程序的另一个模块，不是我做的。

无论如何，最好的解决方案是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;
    }
}

Answer 2

我不确定，但我认为while循环中的最后一行代码是错误的。据我所知，最后一个变量是蛇的尾巴。这意味着last->next = null。在的第二行代码中，将上一行的前一行设为空，在的最后一行代码中，最后一行变为0。我认为修改while循环中的最后一行代码会改变这一点。

last = last->next

Answer 3

您永远不会设置列表的新头部，因为在while循环之后，tmp总是空的。试试这个；

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