create/reverse 链表的最佳方法是什么？

Question

我是编程初学者，我已经学会了如何反转链表。下面是我用来制作一个带有随机值的链表并将其反转的代码。我想知道最好的方法是什么。感谢您的建议！祝你有美好的一天！

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

// node
typedef struct node{
    int number;
    struct node *next;
}node;

// functions
node *reversedList(node *head);
void printList(node *head);
node *create(int size);

int main(void)
{
    srand(time(0));
    // ........
}

node *reversedList(node *curr)
{
    // a->b->c->d
    // d->c->b->a
    node *previous = NULL;
    while(curr->next != NULL)
    {
        node *curr_temp = curr->next;
        curr->next = previous;
        previous = curr;
        curr = curr_temp;
    }
    curr->next = previous;
    return curr;
}

void printList(node *head)
{
    if (head == NULL)
        return;
    printf("%d ",head->number);
    printList(head->next);
}

node *create(int size)
{
    if(size == 0)
        return NULL;
    node *n = malloc(sizeof(node));
    n->number = rand() % 10;
    n->next = create(size - 1);
    return n;   
}

Answer 1

反转 singly-linked 列表的最佳方法是在不调用未定义行为的情况下反转它

在您的函数 reversedList 中，您没有检查传递的指针 curr 是否等于 NULL。所以while循环中的表达式

while(curr->next != NULL)

可以调用未定义的行为。

函数可以这样定义

node * reversedList( node *head )
{
    // a->b->c->d
    // d->c->b->a

    node *curr = head;
    head = NULL;

    while ( curr != NULL )
    {
        Node *tmp = curr;
        curr = curr->next;
        tmp->next = head;
        head = tmp; 
    }

    return head;
}

注意递归函数printList的参数要用限定符const声明，因为列表在函数内部没有变化

void printList(cosnt node *head);

我将按以下方式声明和定义递归函数

FILE * printList( const node *head, FILE *fp )
{
    if ( head )
    {
        fprintf( fp, "%d ", head->number );
    
        printList( head->next, fp );
    }

    return fp;
}

主要你可以写

fputc( '\n', printList( head, stdout ) );

使用这样的函数，您可以在包括文件流在内的任何流中输出列表。

Answer 2

旁注： 奇怪的是，您为反转做了一个迭代解决方案，但为 create 做了一个递归解决方案，并且printList

您的函数非常接近最优。

但是，您 curr->next 两次。不可否认，有了优化器，应该不会有额外的速度损失。

但是，我会简化它。而且，我认为 for 循环可以更简洁：

node *
reversedFor(node *curr)
{
    // a->b->c->d
    // d->c->b->a
    node *prev = NULL;
    node *next;

    for (;  curr != NULL;  curr = next) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
    }

    return prev;
}

编辑： 而且，正如 Vlad 提到的，您在取消引用之前不检查 curr 是否为 non-null。因此，我的上述重构意外地修复了该错误。

以下是我要清理的所有内容：

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

// node
typedef struct node {
    int number;
    struct node *next;
} node;

// functions
node *reversedList(node *head);
node *reversedFor(node *head);
void printList(node *head,const char *tag);
node *create(int size);
node *delList(node *head);

typedef node *(revfnc_p)(node *head);

void
dotest(revfnc_p fnc,const char *tag)
{
    node *list;

    printf("dotest: %s\n",tag);

    list = create(10);
    printList(list,"orig");

    list = fnc(list);
    printList(list,"revd");

    delList(list);
}

int
main(void)
{

    dotest(reversedList,"reversedList");
    dotest(reversedFor,"reversedFor");

    return 0;
}

node *
reversedList(node *curr)
{
    // a->b->c->d
    // d->c->b->a
    node *previous = NULL;

    while (curr->next != NULL) {
        node *curr_temp = curr->next;

        curr->next = previous;
        previous = curr;
        curr = curr_temp;
    }
    curr->next = previous;
    return curr;
}

node *
reversedFor(node *curr)
{
    // a->b->c->d
    // d->c->b->a
    node *prev = NULL;
    node *next;

    for (;  curr != NULL;  curr = next) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
    }

    return prev;
}

void
printList(node *head,const char *tag)
{

    if (tag != NULL)
        printf("%s:",tag);

    for (node *curr = head;  curr != NULL;  curr = curr->next)
        printf(" %d",curr->number);

    printf("\n");
}

node *
create(int size)
{
    node *head = NULL;
    node *prev = NULL;
    node *curr;

    for (int idx = 0;  idx < size;  ++idx) {
        curr = malloc(sizeof(*curr));
        curr->number = idx;
        curr->next = NULL;

        if (head == NULL)
            head = curr;
        else
            prev->next = curr;

        prev = curr;
    }

    return head;
}

node *
delList(node *curr)
{
    node *next;

    for (;  curr != NULL;  curr = next) {
        next = curr->next;
        free(curr);
    }

    return curr;
}

程序输出如下：

dotest: reversedList
orig: 0 1 2 3 4 5 6 7 8 9
revd: 9 8 7 6 5 4 3 2 1 0
dotest: reversedFor
orig: 0 1 2 3 4 5 6 7 8 9
revd: 9 8 7 6 5 4 3 2 1 0

create/reverse 链表的最佳方法是什么？

What is the best way to create/reverse a linked list?

c

linked-list

reverse

singly-linked-list

function-definition