如何反转我在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。你当时的名单是：

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

凡tmpHead是一个临时变量，让您不输于C参考（如B.next现在指向A）你想：

1. 连接B到C使B来后C
2. 组头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。所以，正如我所定义的那样，列表中的第一个真正节点是您的head->next。这意味着您必须调用reverse这样的功能：reverse(& (head->next))或稍微修改该功能。

此外，请注意，您不应该投射malloc的结果。 Do I cast the result of malloc?