c - 如何反转我在 C 中创建的链接列表

Question

我创建了一个链接列表，但不知道如何反转它。我知道这个算法，但我认为我在创建列表时犯了一个错误。反向功能可能会发生什么变化才能起作用。 代码如下:

typedef struct Node{
    int data;
    struct Node* next;
} node;
node* head;
int count;
void insertAtBegin(int value){
    if(head==NULL){
        head = (node*)malloc(sizeof(node));
        head->data = 0;
        head->next = NULL;
    }
    node* newNode = (node*)malloc(sizeof(node));
    newNode->data = value;
    newNode->next = head->next;
    head->next = newNode;
    count++;
}

void display(){
    node* temp = (node*)malloc(sizeof(node));
    temp = head;
    while(temp->next!=NULL){
        printf("%d\t",temp->next->data);
        temp = temp->next;
    }
    printf("\n");
}

void reverse(){
    node *p, *q, *r;

    p = q = r = head;
    p = p->next->next;
    q = q->next;
    r->next = NULL;
    q->next = r;

    while (p != NULL){
        r = q;
        q = p;
        p = p->next;
        q->next = r;
    }
    head = q;
}

void main(){
    insertAtBegin(5);
    insertAtBegin(6);
    display();
    reverse();
    display();
    printf("\nSize of linked list is %d",count);
}

Answer 1

假设您有以下列表:

head = n0
n0 -> ... -> A -> B -> C -> D -> E -> ... -> nN -> NULL

您想要反转到:

head = nN
nN -> ... -> E -> D -> C -> B -> A -> ... -> n0 -> NULL

现在，让我们考虑一下列表开头已经反转并且您正在处理节点 C 的情况。您当时的 list 是:

head = B
B -> A -> ... -> n0-> NULL
tmpHead  = C
C -> D -> E ... -> nN -> NULL

其中 tmpHead 是一个临时变量，它允许您不会丢失对 C 的引用(因为 B.next 现在指向 A)您想要:

1. 将B连接到C，以便B位于C之后
2. 将 head 设置为 C，即反转列表的新头
3. 将 D 保留在临时变量 tmpHead 中，以便您仍然可以访问它

反转则变为:

node * tmp   = tmpHead.next;  // 3. part 1
tmpHead.next = head;          // 1.
head         = tmpHead;       // 2.
tmpHead      = tmp;           // 3. part 2

停止条件非常明显:当到达列表末尾时，必须停止，因此，当tmpHead为NULL时。对于初始化来说，head指向反转部分，tmpHead指向非反转部分。因此，tmpHead 必须设置为 head，并将 head 设置为 NULL。

最后，您将获得以下函数，该函数将指向列表的第一个节点的指针作为输入参数

void reverse(node ** head)
{
  node * tmpHead = (* head);
  (* head)       = NULL;

  while(tmpHead)
  {
    node * tmp    = tmpHead->next;
    tmpHead->next = (* head);
    (* head)      = tmpHead;
    tmpHead       = tmp;
  }
}

请注意，在列表开头插入新节点的方式存在一个“问题”:您始终保留一个数据设置为 0 的“幻影”节点，并且调用 头。因此，正如我所定义的，列表的第一个实际节点是您的 head->next。这意味着您必须像这样调用 reverse 函数:reverse(& (head->next)) 或稍微修改该函数。

另外，请注意，您不应该强制转换 malloc 的结果。 Do I cast the result of malloc?