c-在单链表中按升序插入

Question

假设我有一个按升序排列的元素单链列表，看起来像：

A->B->D->E

我想在B和D之间插入C。我知道如何将C指向D，但我不知道如何将B指向C，因为链表没有跟踪上一个节点。

Answer 1

在向下扫描节点列表时，必须保留两个指针：一个指向您感兴趣的当前节点，另一个指向上一个节点。

Answer 2

可能的实现如下：

struct node {
    int value;
    struct node *next;
};
void sorted_insert(struct node **head, struct node *element) {
    // Is the linked list empty?
    if (*head == NULL) {
        element->next = NULL;
        *head = element;
        return;
    }
    // Should we insert at the head of the linked list
    if (element->value < (*head)->value) {
        element->next = *head;
        *head = element;
        return;
    }
    // Otherwise, find the last element that is smaller than this node
    struct node *needle = *head;
    while (true) {
        if (needle->next == NULL)
            break;
        if (element->value < needle->next->value)
            break;
        needle = needle->next;
    }
    // Insert the element
    element->next = needle->next;
    needle->next = element;
    return;
}

Answer 3

您不需要将B指向C，也不需要维护指向前一个元素的指针。一种方法是：

1. 步骤到节点D

2. malloc()新节点

3. 将数据和next成员从节点D复制到您的新节点

4. 将节点C的数据复制到现有节点D（现在成为节点C）

5. 将旧节点D的next成员指向新节点。

例如，排除在列表顶部插入的可能性：

void insert(struct node * head, const int data, const size_t before)
{
    assert(before > 0);
    struct node * node = head;
    while ( before-- && node ) {
        node = node->next;
    }
    if ( !node ) {
        fprintf(stderr, "index out of rangen");
        exit(EXIT_FAILURE);
    }
    struct node * new_node = malloc(sizeof *new_node);
    if ( !new_node ) {
        perror("couldn't allocate memory for node");
        exit(EXIT_FAILURE);
    }
    new_node->data = node->data;
    new_node->next = node->next;
    node->next = new_node;
    node->data = data;
}

Answer 4

在遍历列表时，为什么不跟踪"上一个"节点？请原谅任何语法上的不足，因为我还没有编译过这篇文章，但这应该会给你一个想法。

struct node {
  char name[ 10 ];
  struct node *next;
};
struct list {
  struct node *head;
};
void insert_C(struct list *list) {
  struct node *new_node = malloc(sizeof(struct node));
  if( new_node == NULL ) {
    /* Error handling */
  }
  strcpy(new_node->name, "C");
  struct node *pnode;
  struct node *prev_node = NULL;
  for( pnode = list->head; pnode->next != null; pnode = pnode->next ) {
    if( !strcmp(pnode->name, "D") ) {
      if( prev_node == NULL ) {
        /* The 'C' node is going to be the new head. */
        new_node->next = list->head;
        list->head = new_node;
      }
      else {
        prev_node->next = new_node;
        new_node->next = pnode;
      }
      break;
    } 
    /* Remember this node for the next loop iteration! */
    prev_node = pnode;
  }
}