我需要实现一个函数来反转一个链表,但我不知道如何返回一个新形成的链表作为结果。

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/

10-10 18:23
查看更多