在每两个之间插入列表中的元素

Question

我需要编写一个函数，在单链表中每两个现有节点之间插入一个新节点，其值等于这两个节点值的差值。

例如，如果我们有列表 1→2→5→7 结果应该是 1→1→2→3→5→2→7，因为 2-1=1, 5-2=3 and 7 -5=2.

这是我的尝试：

struct Node{
    int v;
    struct Node* next;
};
void insert(struct Node** headPtr){
    struct Node* curr = *headPtr;
    struct Node* new = malloc(sizeof(struct Node));
    while(curr->next!=NULL){
        new->v=curr->next->v-curr->v;
        new->next=curr->next;
        curr->next=new;
        curr=curr->next;
    }
}
void addRear(struct Node** headPtr, int v_new){
    struct Node* new = malloc(sizeof(struct Node));
    new->v=v_new;
    new->next=NULL;
    if(*headPtr==NULL){
        *headPtr=new;
    }else{
        struct Node* curr = *headPtr;
        while(curr->next!=NULL){
            curr=curr->next;
        }
        curr->next=new;
    }
}
void print(struct Node* head){
    struct Node* curr = head;
    while(curr!=NULL){
        printf("%d ",curr->v);
        curr = curr->next;
    }
}

但是当我运行 main 中的以下内容时，我没有得到任何结果。这是我的 main 代码：

struct Node* head=NULL;
addRear(&head,1);
addRear(&head,2);
addRear(&head,5);
addRear(&head,7);
print(head);
printf("\n");
insert(&head);
print(head);

Answer 1

两期：

您只创建了一个个新节点。将新节点的创建移动到循环内。
curr=curr->next 是不正确的，因为那时 curr 将等于 new 节点。因此，在下一次迭代中，您将不会更接近列表的末尾。循环永远不会结束。相反，你应该做 curr = new->next.

这是更正后的代码：

void insert(struct Node** headPtr){
    struct Node* curr = *headPtr;
    while (curr->next != NULL) {
        struct Node* new = malloc(sizeof(struct Node)); // <---
        new->v = curr->next->v - curr->v;
        new->next = curr->next;
        curr->next = new;
        curr = new->next; // <---
    }
}

在每两个之间插入列表中的元素

Inserting elements in list, between every two

linked-list

singly-linked-list