c-创建/反转链接列表的最佳方式是什么

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

反转单链表的最佳方法是在不调用未定义行为的情况下进行反转

在函数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之前，您不会检查它是否为非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: %sn",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