反转链表列表

Question

我试图反转链表，但我一直遇到问题。我终于发现错误并修复了它，但是我不明白为什么我最后的方法不起作用。下面的代码是成功反转链表的代码。

void reverse_list(list** head)
{
    list* currNode = *head;
    list* prevNode = NULL;
    list* tmpNode;

    while(1)
    {
        tmpNode = currNode->next;
        currNode->next = prevNode;
        if(tmpNode == NULL)
        {
            *head = currNode;
            break;
        }
        prevNode = currNode;
        currNode = tmpNode;
    }

}

但是，下面的代码不起作用。两者都使用双指针，但在这一个中，我两次取消引用 head 以到达实际对象并将其分配给 *currNode。当我运行这段代码时，它最终进入无限循环并且缺少最后一项。例如，如果项目是 1、2、3、4、5，那么反过来就是 5、4、3、2，它会一直打印相同的列表。我不明白为什么这种方法不起作用，因为我正在访问实际对象（通过取消引用两次）并为其分配一个新对象 (*currNode)。

void reverse_list(list** head)
{
    list* currNode = *head;
    list* prevNode = NULL;
    list* tmpNode;

    while(1)
    {
        tmpNode = currNode->next;
        currNode->next = prevNode;
        if(tmpNode == NULL)
        {
            **head = *currNode;
            break;
        }
        prevNode = currNode;
        currNode = tmpNode;
    }

}

下面的代码与上面的代码有同样的问题。我采用了与上述代码相同的方法，只是这个代码使用了一个指针。

void reverse_list(list* head)
{
    list* currNode = head;
    list* prevNode = NULL;
    list* tmpNode;

    while(1)
    {
        tmpNode = currNode->next;
        currNode->next = prevNode;
        if(tmpNode == NULL)
        {
            *head = *currNode;
            break;
        }
        prevNode = currNode;
        currNode = tmpNode;
    }

}

如果能帮助理解这一点，我们将不胜感激。谢谢！

Answer 1

不同级别的间接寻址。

给定list** head，*head是head指向的值，指向Node，list *。我们又取消了一次引用，**head 取消了对 list * 的引用，然后又取消了对 list 的引用。我们都用完了指针，并且正在访问该行末尾的对象。所以

**head = *currNode;

取消引用两个指针，一直返回到对象。这是为对象赋值，而不是为指向对象的指针赋值。不是通过更新指针来更改列表的链接，而是 list head 最终指向的内容已更改为匹配 currNode，破坏了列表的完整性。

*head = currNode;

仅取消对头部靠近对象一级的引用。这里我们是对指针进行操作，改变连接。

在最后一个例子中我们有

*head = *currNode;

这类似于第一次失败的尝试。它正在分配值而不是更改指针。

Answer 2

对于初学者来说，由于这些行，所有三个函数在为空列表调用时通常都可以调用未定义的行为

list* currNode = head;
//...
tmpNode = currNode->next;

因为使用了一个空指针来访问内存。

在此 if 语句的第二个函数中

    if(tmpNode == NULL)
    {
        **head = *currNode;
        break;
    }

原来的第一个节点被最后一个节点覆盖

**head = *currNode;

所以退出函数后，原来的指针头仍然指向原来的第一个节点，被链表的最后一个节点覆盖。因此，一个实际数据将丢失，并且会发生内存泄漏。

至于第三个函数，只要指出该函数按值接受指向头节点的指针即可。

void reverse_list(list* head)

即函数处理的是原始变量head值的拷贝。更改副本不会影响原始指针。原来的指针还是会指向第一个节点。

函数可以通过以下方式看起来更简单

void reverse( list **head )
{
    list *current = *head;
    *head = NULL;
        
    while ( current != NULL )
    {
        struct Node *tmp = current;
        current = current->next;
        tmp->next = *head;
        *head = tmp;
    }
}

这是一个演示程序。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node *next;
} list;

int push_front( list **head, int data )
{
    list *new_node = malloc( sizeof( list ) );
    int success = new_node != NULL;
    
    if ( success )
    {
        new_node->data = data;
        new_node->next = *head;
        *head = new_node;
    }
    
    return success;
}

void display( const list *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d -> ", head->data );
    }
    
    puts( "null" );
}

void reverse( list **head )
{
    list *current = *head;
    *head = NULL;
        
    while ( current != NULL )
    {
        list *tmp = current;
        current = current->next;
        tmp->next = *head;
        *head = tmp;
    }
}

int main(void) 
{
    const int N = 10;
    
    list *head = NULL;
    
    display( head );
    
    reverse( &head );
    
    display( head );
    
    putchar( '\n' );
    
    for ( int i = 0; i < N; i++ )
    {
        push_front( &head, i );
    }
    
    display( head );
    
    reverse( &head );
    
    display( head );
    
    return 0;
}

程序输出为

null
null

9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

反转链表列表

Reversing a linked list list

c

reverse

linked-list

singly-linked-list

function-definition