我旋转双向链表的逻辑有什么问题？

Question

给定一个双向链表，将链表逆时针旋转P个节点。这里 P 是给定的正整数，小于链表中的节点数 (N)。第一行包含测试用例的数量。每个测试用例由两行组成，一行指定 N 和 P，另一行指定值列表。

示例：输入：

1
6 2
1 2 3 4 5 6

输出：

3 4 5 6 1 2

我已经编写了一个函数来进行给定的旋转。我不断收到运行时错误。官方问题定义可以参考https://practice.geeksforgeeks.org/problems/rotate-doubly-linked-list-by-p-nodes/1/

struct node *rotate(struct node *head){ 
    int num, count=1;
    struct node *current, *nnode;
    current=head;
    printf("\nEnter the number across which you wanna rotate: ");
    scanf("%d", &num);
    if(num==0){
        return;
    }
    while(count<num && current!=NULL){
        current=current->next;
        count++;
    } 
    if(current==NULL){
        return;
    }
    nnode=current;
    while(current->next!=NULL){
        current=current->next;
    }
    current->next=head;
    head->prev=current;
    head=nnode->next;
    head->prev=NULL;
    nnode->next=NULL;
    return head;
}

Answer 1

除非你坚持使用线性列表，否则我建议你使用循环列表，即最后一个 link 的 next 指向第一个 link.您可以像使用任何其他“线性”列表一样使用它们；当你循环遍历它们时，你只想检查你是否 return 到你开始的地方，而不是测试你是否到达 NULL。当你创建 links 时，你会遇到一个特殊情况，有时如果你有一个空列表，当你插入它们时，但没有比其他情况更糟糕的了。（如果你不需要像旋转那样移动头部，那么你可以用一个虚拟节点来处理它，并且你可以摆脱很多非循环列表的特殊情况）。

循环列表的一些简单代码（没有虚拟 link，因此列表可以是 NULL）如下所示：

struct link {
  int value;
  struct link *prev;
  struct link *next;
};

static inline
void connect_neighbours(struct link *x)
{
  x->next->prev = x;
  x->prev->next = x;
}
static inline
void link_after(struct link *x, struct link *y)
{
  y->prev = x;
  y->next = x->next;
  connect_neighbours(y);
}
#define link_before(x, y) \
  link_after((x)->prev, y)

struct link *new_link(int val,
                      struct link *prev,
                      struct link *next)
{
  struct link *link = malloc(sizeof *link);
  if (!link) return 0;

  link->value = val;
  if (prev == 0 || next == 0) {
    // make a link circular if we don't have prev/next
    link->next = link->prev = link;
  } else {
    // otherwise, just set the links
    link->prev = prev;
    link->next = next;
  }
  return link;
}

这是创建 link 的代码，如果我们不提供指向 [=37= 的指针，linking prev 和 next 到节点本身]s，并在 link 之前或之后放置一个新的 link。 link_after() 和 link_before() 操作当然会失败，如果你给它们 NULL 指针，所以你不能使用它们，直到你有一个至少有一个 link 的列表它。

要运行通过一个列表，比如要打印出来，可以这样写代码：

void print_list(struct link *head)
{
  if (!head) {
    printf("[]\n");
    return;
  }
  printf("[ ");
  printf("%d ", head->value);
  for (struct link *link = head->next;
       link != head;
       link = link->next) {
    printf("%d ", link->value);
  }
  printf("]\n");
}

for-条件，我们检查我们是否回到了头，是我们如何识别我们已经完成。空列表的特殊情况，以及处理循环外的第一个 link ，如果你有一个虚拟 link 也不是必需的，但是对于旋转操作，如果我们没有假。如果我们不这样做，那么旋转就像遵循 next 或 prev 指针正确的次数一样简单：

struct link *rotate(struct link *x, int rot)
{
  if (rot > 0) {
    for (; rot; rot--) x = x->next;
  } else {
    for (; rot; rot++) x = x->prev;
  }
  return x;
}

使用上面的代码，您可以像这样创建和旋转列表：

int main(void)
{
  struct link *x = 0;
  print_list(x);

  // not checking allocation errors here!
  x = new_link(1, 0, 0);
  for (int i = 2; i <= 5; i++)
    link_before(x, new_link(i, 0, 0));
  print_list(x);

  print_list(rotate(x, 2));
  print_list(rotate(x, -2));

  return 0;
}

我旋转双向链表的逻辑有什么问题？

What is wrong with my logic to rotate a doubly linked list?

c

data-structures

linked-list

doubly-linked-list