сортировка четных и нечетных чисел в связанном списке

Question

Im пытается написать функцию, которая принимает случайный список и сортирует его (в c), чтобы четные числа были первыми, делая это, не создавая второй список. То, что я пытаюсь сделать, - это перемещение вновь найденного четного числа в начало списка (что делает предыдущую главу элементом seconnd). Брус понять, почему мои указатели получить перепутано, хотя -

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

void sortlist(node *head) { 
    if (head == NULL) { 
     printf("Empty list \n"); 
    } 
    node *index1 = head->next; 
    node *oldhead; 
    if (index1 == NULL) { 
     return; 
    } 
    while (index1 != NULL) { 
     if (index1->data % 2 == 0) { 
      oldhead = head; 
      head = index1; 
      head->next = oldhead; 
     } 
     index1 = index1->next; 
    } 
} 

Answer 1

Основная идея: Предположим, у вас есть список, как показано ниже.

1-> 3-> 2-> 4

Если вы хотите, чтобы элемент 2 новый голова, вы должны сделать две вещи.

• Unlink элемент 2 и сделать следующий элемент 3 в 4. [которого вы не указали в своем коде]
• Создайте новый узел и сделайте его новым главой списка.

Тогда список будет выглядеть как 2->1->3->4. Снова сделав то же самое для элемента 4, он будет выглядеть как 4->2->1->3.

Итак, я считаю, вам нужно (предварительно) что-то вроде этого.

void sortlist(node *head) { 
    if (head == NULL) { 
     printf("Empty list \n"); 
    } 
    node *current = head->next; 
    node *previous = head; 
    while(current != NULL){ 
     if(current->data % 2 == 0){ 
      previous->next = current->next; 
      current->next = head; 
      head = current; 
     } else{ 
      previous = previous->next; 
      //previous = current; [an equivalent statement] 
     } 
     current = previous->next; 
    } 
} 

Альтернативный подход, если вы хотите создать новый узел и сделать его главой списка.

void sortlist(node *head) { 
    if (head == NULL) { 
     printf("Empty list \n"); 
    } 
    node *current = head->next; 
    node *previous = head; 
    while(current != NULL){ 
     if(current->data % 2 == 0){ 
      previous->next = current->next; 
      node* new_node = (struct node*) malloc (sizeof (struct node)); 
      new_node->data = current->data; 
      new_node->next = head; 
      head = new_node; 
     } else{ 
      previous = previous->next; 
     } 
     current = current->next; 
    } 
} 

Update: Я проверил как фрагмент кода. Работает!

Answer 2

Этого недостаточно: при перемещении узла к голове, вам необходимо также направить его предыдущего к его следующему. Поскольку ваш список связан только в одном направлении, вам нужно следить за тем, что было раньше.

Кроме того, отправка указателя на голову, как это, по значению, не изменит его в вызывающем абоненте, чтобы вызывающий абонент потерял трек заголовка списка. Таким образом, вам нужно передать указатель головы таким образом, что он может быть изменен и извлекаться, то есть послать указатель на этот указатель:

void sortlist(node** head) { 
    if (*head == NULL) { 
     printf("Empty list \n"); 
    } 
    node *index1 = (*head)->next; 
    node *prev = *head; 

    while (index1 != NULL) { 
     if (index1->data % 2 == 0) { 
      prev->next = index1->next; 
      index1->next = *head; 
      *head = index1; 
     } 
     else { 
      prev = index1; 
     } 
     index1 = prev->next; 
    } 
} 

Answer 3

Не понятно, почему вы пропускаете головы себя и начать с head-> следующая.

Также головной узел должен быть передан по ссылке, потому что голова изменяется в функции.

И не имеет смысла выводить сообщение о том, что список пуст, потому что вызывающий может проверить себя перед вызовом функции, является ли список пустым, не так ли?

Функция может выглядеть следующим образом

void sortlist(node **head) 
{ 
    for (node **current = head; *current != NULL;) 
    { 
     if ((*current)->data % 2 == 0 && current != head) 
     { 
      node *tmp = *current; 
      *current = (*current)->next; 
      tmp->next = *head; 
      *head = tmp; 
     } 
     else 
     { 
      current = &(*current)->next; 
     } 
    } 
} 

Например, если список содержит следующий пункт

0 1 2 3 4 5 6 7 8 9 

затем после вызова функции она будет выглядеть

8 6 4 2 0 1 3 5 7 9