вставки в односвязный список в порядке возрастания

Question

Скажем, у меня есть односвязный список элементов в порядке возрастания, который выглядит как:

A-> B-> D-> E

I хотите вставить C между B и D. Я знаю, как указывать 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. Направьте элемент next старого узла D на новый узел.

Например, исключая возможность введения во главе списка:

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 range\n"); 
     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; 
    } 

}