我需要实现一个函数来反转一个链表,但我不知道如何返回一个新形成的链表作为结果。
typedef struct node_t* Node;
struct node_t {
int n;
Node next;
};
// create a new node with value n
Node nodeCreate(int n)
{
Node node = malloc(sizeof(*node));
if (node == NULL) return NULL;
node->n = n;
node->next = NULL;
return node;
}
// reversing the linked list
Node reverseList(Node list)
{
if (list == NULL) return NULL;
Node current, prev, next;
current = rev_head;
prev = NULL;
while( current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
list = prev;
return list;
}
这是我到目前为止写的代码。
如何将此反向链接列表插入函数
reverseList
自身中的其他新链接列表? 最佳答案
您在原始列表中的节点周围进行切换,然后进行修改-这意味着您只有一个列表,并修改其节点。
如果这正是您想要的,那么您的代码可能会工作(只要您修复了从任何地方出现的rev_head
变量之类的问题),并且列表的新头(位于prev
变量上):这意味着您的代码应该可以正常工作。
(重要的是typedef不能隐藏指针,我建议更改它。)
您似乎不太了解的是,对于这种o结构,任何节点都充当列表的头—没有“列表”类型,只有“节点”类型—如果您碰巧选择了列表中间的任何节点,那么它将只表示一个部分列表,也从该节点开始。所以当你改变你的前一个“最后一个”节点,指向它的前一个“前一个”作为它的“下一个”时,那就是:这个节点现在是头。
(这种“node==list”等式的例外情况是,当反转算法运行时——此时,您有指向一个方向的节点和指向另一个方向的节点,而额外的“next”和“prev”变量提供修复问题所需的信息。如果这是生产代码,则这部分代码必须在线程锁中受到保护)
否则,如果要生成列表的反向副本,则必须沿途复制旧节点,并仅修复它们指向的位置。
#include <stdlib.h>
#include <string.h>
typedef struct node_t Node;
struct node_t {
int n;
Node next;
};
// create a new node with value n
Node *nodeCreate(int n) {
Node *node = malloc(sizeof(*node));
if (node == NULL) return NULL;
node->n = n;
node->next = NULL;
return node;
}
void nodeCopy(Node *node_dst, Node *node_src) {
if (node_src == NULL || node_dst == NULL || abs(node_dst - node_src) < sizeof(Node)) {
return
}
memcpy(node_dst, node_src, sizeof(Node));
}
// reversing the linked list
Node *reverseList(Node *list) {
Node *new_list, *prev;
if (list == NULL) return NULL;
new_list = nodeCreate(0);
nodeCopy(new_list, list);
new_list->next=NULL;
prev = new_list;
while(list->next != NULL) {
list = list->next;
new_list = nodeCreate(0);
nodeCopy(new_list, list);
new_list->next=prev;
prev = new_list;
}
return new_list;
}
关于c - 反向链表返回新链表,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/47696400/