反向链表返回新链表

Question

我需要实现一个反转链表的函数，但是我不知道如何返回一个新形成的链表。

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 it self函数中的另一个新链表中？

Answer 1

您正在处理原始列表上的节点，然后在适当的位置进行修改-这意味着您只有一个列表，并修改了它的节点。

如果这是您想要的，那么您的代码可能会正常工作(只要您修复了像rev_head变量这样的东西，它就出现在您的prev变量上)-以及列表的新头部:这意味着您的代码应该可以正常工作。

(但重要的是类型定义函数不能隐藏指针，我建议对其进行更改。)

你似乎没有很好理解的是，对于这种o结构，任何节点都作为列表的头部工作-没有" list“类型，只有" node”类型-如果你碰巧选择了列表中间的任何节点，那将只表示一个部分列表，也从该节点开始。因此，当您将先前的“最后一个”节点更改为指向其先前的"antecessor“作为其”下一个“时，就是这样:该节点现在是head。

(这种“节点下一个列表”相等的例外情况是当反向算法正在运行时-此时您有指向一个方向的节点和指向另一个方向的节点，而额外的“==”和"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;
}

Answer 2

您可以简单地为原始列表中的每个节点创建一个新节点，并以相反的顺序设置链接。代码可以是：

Node createReversedList(Node node) {
    Node result = NULL;
    while (node != NULL) {
        Node n = nodeCreate(node->n);
        n->next = result;
        result = n;
        node = node->next;
    }
    return result;
}

Answer 3

有一种简单的方法可以反转链表

您可以简单地创建一个新的链表，并在链表的开头添加每个节点，这将以相反的顺序创建相同的链表

Node* revList(Node *start){
Node *startRev=NULL,*temp,*newNode;
temp = start;
while (temp->next!=NULL){
    newNode = (Node *) malloc (sizeof(Node));
    //Code for copying data from temp to new node

    if(startRev == NULL){
        startRev = newNode;
    }
    else {
        newNode->next = startRev;
        startRev = newNode;
    }
    temp = temp->next;
}
return startRev;
}