反向双链表

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

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

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

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

Answer 1

我不确定，但我认为你的 while 循环中的最后一行代码是错误的。据我了解，最后一个变量是蛇的尾巴。这意味着 last->next = null。在 while 的第二行代码中，while 中的 previous of last null 和最后一行代码中的 while last 变为 0。我认为更改 while 循环中的最后一行代码会改变这一点。

last = last->next

Answer 2

您永远不会设置列表的新头部，因为 tmp 在 while 循环后始终为 NULL。试试这个；

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

Answer 3

您必须将 *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;
    }
}

反向双链表

Reverse double linked list

c

reverse

pointers

linked-list

list