单链表在中间添加节点

Question

class List {
  ListNode *head;
  ListNode *prev;
};
class ListNode {
  int data;
  ListNode *next;
  friend class List;
  ListNode(int d, ListNode *n) : data(d), next(NULL) {}
  void insertM(int d) {
    ListNode *ptr, *temp, *curr;
    ptr = head;
    while (ptr->data < d) {
      prev = ptr;
      ptr = ptr->next;
    } // end while
    temp = prev->next;
    curr = new ListNode(d, ptr);
    curr->next = prev->next; // or temp->next
    prev->next = curr;
    ;
  }
};
List mylist;

在这个函数中，我尝试在链表中间添加一个节点。其他功能可以将项目添加到背面和正面就可以了。当我在列表中间添加时，我的上一个>下一个链接到 curr 很好，但 curr->next 指向 NULL。

在过去的 1.5 小时内，我一直在尝试使该程序正常工作。我会感谢您的帮助。这是家庭作业。

Answer 1

您需要使用的一般过程是：

1. 向下浏览next指针，直到到达要插入的节点（称为 A）
2. 更改插入的节点 （B） 的next指针以匹配 A 的next指针
3. 更改 A 的next指针以指向 B

从代码中可以看出，您正在尝试维护整数的排序列表。这是家庭作业，您可能不会获得代码片段，但是通过浏览代码，我不得不问为什么您在节点构造函数中采用下一个参数，然后将下一个值设置为 null。如果没有看到您的其余代码，我不能肯定地说，但我会将第 9 行的next(NULL)更改为 next(n) ，然后删除底部附近的curr->next行