递归地在链表的末尾插入一个节点

Question

typedef struct node
{
    int a;
    struct node *next;
}node;
void generate(struct node **head)
{
    int num = 10, i; //the num here is the length
    struct node *temp;

    for (i = 0; i < num; i++)
    {
        temp = (struct node*)malloc(sizeof(struct node));
        temp->a = 10-i;
        if (*head == NULL)
        {
            *head = temp;  //each time add another node to the start
            (*head)->next = NULL;
        }
        else
        {
            temp->next = *head;
            *head = temp;
        }
    }
}
void addSpecific(node* head,int n)
{
    node* temp = NULL;
    if (head->next == NULL)
    {
        temp = (node*)malloc(sizeof(node*)); //allocating memory
        (temp)->a = n;  //adding the wanted value
        (temp)->next = NULL; //making the new node to point to the end
        head->next = temp; //and the previous one to point to temp
    }
    else
    {
        addSpecific(head->next, n); //if this is not the wanted node we need to move to the next node
    }
}
void deleteNode(struct node **head)
{
    struct node *temp;
    while (*head != NULL)
    {
        temp = *head;
        *head = (*head)->next; //going to the next node
        free(temp); //free the allocated memory
    }
}
int main()
{
    struct node *head = NULL;

    generate(&head);
    addSpecific(head, 7);
    display(head);
    deleteNode(&head);
    system("PAUSE");
    return 0;
}

我试图使用递归在末尾插入新节点，但是释放内存（删除）函数进行了扩展，我找不到问题所在。我尝试了生成函数并在末尾添加了节点并且它起作用了但是编译器提醒我 "heap corruption".

Answer 1

函数可以看成下面的演示程序

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

typedef struct node
{
    int a;
    struct node *next;
} node;

void addSpecific( node **head, int n )
{
    if ( *head == NULL )
    {
        *head = malloc( sizeof( node ) ); //allocating memory
        ( *head )->a    = n;  //adding the wanted value
        ( *head )->next = NULL; //making the new node to point to the end
    }
    else
    {
        addSpecific( &( *head )->next, n ); //if this is not the wanted node we need to move to the next node
    }
}

void display( node *head )
{
    for ( ; head != NULL; head = head->next ) printf( "%d ", head->a );
    printf( "\n" );
}

int main( void ) 
{
    const int N = 10;
    node *head = NULL;

    for ( int i = 0; i < N; i++ ) 
    {
        addSpecific( &head, i );

        display( head );
    }

    return 0;
}

程序输出为

0 
0 1 
0 1 2 
0 1 2 3 
0 1 2 3 4 
0 1 2 3 4 5 
0 1 2 3 4 5 6 
0 1 2 3 4 5 6 7 
0 1 2 3 4 5 6 7 8 
0 1 2 3 4 5 6 7 8 9

至于函数deleteNode那么可以这样找例如下面的方式

void deleteNode( node **head )
{
    for ( node *current = *head; current != NULL; )
    {
        node *temp  = current;
        current = current->next; //going to the next node
        free( temp ); //free the allocated memory
    }

    *head = NULL;
}

至于这个函数的实现

void deleteNode( node **head )
{
    while ( *head != NULL )
    {
        node *temp  = *head;
        head = &( *head )->next; //going to the next node
        free( temp ); //free the allocated memory
    }
}

然后它有未定义的行为，因为它试图访问已删除的结构对象的数据成员。

或者您可以使函数递归。例如

void deleteNode( node **head )
{
    if ( *head != NULL )
    {
        deleteNode( &( *head )->next );
        free( *head );
        *head = NULL;
    }
}

Answer 2

有点跑题了，但是用两个指针维护单链表比用一个指针维护起来还是很方便的。这样您就可以在 O(1) 中添加和附加列表，而无需使用递归。例如：

struct Node
{
    struct Node* next;
};

struct List
{
    struct Node *head, **tail;
};

void List_init(struct List* list) {
    list->head = 0;
    list->tail = &list->head;
}

void List_append(struct List* list, struct Node* node) {
    node->next = 0;
    *list->tail = node;
    list->tail = &node->next;
}

void List_prepend(struct List* list, struct Node* node) {
    node->next = list->head;
    list->head = node;
    if(list->tail == &list->head)
        list->tail = &node->next;
}

void List_remove(struct List* list, struct Node* node) {
    struct Node *cur = list->head, **prev = &list->head;
    while(cur && cur != node) {
        prev = &cur->next;
        cur = cur->next;
    }
    if(cur) {
        if(!(*prev = node->next))
            list->tail = prev;
    }
}

Answer 3

# For reference:
#
# SinglyLinkedListNode:
#     int data
#     SinglyLinkedListNode next


def insertNodeAtTail(node, data):
    if node is None:
        last = SinglyLinkedListNode(node_data=data)
        last.next = None
        return last
    
    if node.next is None:
        last = SinglyLinkedListNode(node_data=data)
        last.next = None
        node.next = last
        return node
    
    node.next = insertNodeAtTail(node.next, data)

    return node

递归地在链表的末尾插入一个节点

inserting a node at the end of linked list recursivly

c

recursion

pointers

linked-list

singly-linked-list