Разделить связанный список на два других списка, один с нечетными индексами, другой с четными индексами

Question

Заданный вопрос написать функцию split(), которая копирует содержимое связанного списка в два других связанных списка. Функция копирует узлы с четными индексами (0,2 и т. Д.) В EvenList и узлы с нечетными индексами в oddList. Исходный связанный список не должен изменяться. Предположим, что evenlist и oddlist будут переданы в функцию в виде пустых списков (* ptrEvenList = * ptrOddList = NULL).

В моей программе он может отображать начальный список. Хотя в двух других списках есть что-то не так. И это приводит к завершению работы программы.

#include<stdio.h> 
#include<stdlib.h> 

#define SIZE 9 

// определить структуру списка узлов

typedef struct node{ 
    int item; 
    struct node *next; 
}ListNode; 

// вызываем функции

int search(ListNode *head,int value); 
void printNode(ListNode *head); 
void split(ListNode *head,ListNode **OddList,ListNode **EvenList); 

// главная функция

int main(){ 
    ListNode *head=NULL; 
    ListNode *temp; 
    ListNode *OddList=NULL; 
    ListNode *EvenList=NULL; 

// в вопрос, он попросил меня передать два пустых списка в Функция 'slipt'

int ar[SIZE]={1,3,5,2,4,6,19,16,7}; 
    int value=0; 
    int i; 

    head=(struct node*)malloc(sizeof(ListNode)); 
    temp=head; 
    for(i=0;i<SIZE;i++){ 
     temp->item=ar[i]; 
     if(i==(SIZE-1)) //last item 
      break; 
     temp->next=(struct node*)malloc(sizeof(ListNode)); 
     temp=temp->next; 
    } 
    temp->next=NULL; 
    printf("Current list:"); 
    printNode(head); 

    split(head,&OddList,&EvenList); 


return 0; 
} 

**** !!!!!!!!! проблема, я думаю, в этой части.

void split(ListNode *head,ListNode **ptrOddList,ListNode **ptrEvenList){ 
    int remainder; 
    ListNode *tempO,*tempE,*temp; 



    if (head==NULL) 
     return; 
    else{ 
     temp=head; 

     *ptrOddList=(struct node*)malloc(sizeof(ListNode)); 
     *ptrEvenList=(struct node*)malloc(sizeof(ListNode)); 

     tempO=*ptrOddList; 
     tempE=*ptrEvenList; 

     while(temp!=NULL){ 
      remainder=temp->item%2; 

      if(remainder==0){ 
       tempE->next=(struct node*)malloc(sizeof(ListNode)); 
       tempE->item=temp->item; 
       tempE=tempE->next; 
      } 
      else{ 
       tempO->next=(struct node*)malloc(sizeof(ListNode)); 
       tempO->item=temp->item; 
       tempO=tempO->next; 
      } 
      temp=temp->next; 
     } 
     tempE=NULL; 
     tempO=NULL; 

// Я также попытался tempE->next=NULL; и tempO->next=NULL // программа может работать, если я могу изменить его, как и выше, но последние две цифры, показанные будут две случайные числа.

 printf("Even List:"); 
     printNode((*ptrEvenList)); 
     printf("Odd List:"); 
     printNode((*ptrOddList)); 
    } 
} 

---

// функция используется для распечатки результатов

void printNode(ListNode *head){ 
    if (head==NULL) 
     return; 
    while(head!=NULL){ 
     printf("%d ",head->item); 
     head=head->next; 
    } 
    printf("\n"); 
} 

Answer 1

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

Что нужно сделать, это сохранить указатель на указатель на узел для каждого списка. Это будет указатель на «следующий» указатель последнего узла в списке или указатель на заголовок списка, если список пуст. Следующие указатели и указатели списка должны начинаться с NULL.

Когда вы назначаете новый узел, установите последний «следующий» указатель, чтобы указать на новый узел, используя указатель на указатель на узел.

Answer 2

void split(ListNode *head, ListNode **ptrOddList, ListNode **ptrEvenList){ 

    for(; head ; head= head->next) { 
     ListNode *temp; 

     temp = malloc(sizeof *temp); 
     memcpy (temp, head, sizeof *temp); 

     if (temp->item %2) { *ptrOddList = temp; ptrOddList = &temp->next;} 
     else { *ptrEvenList = temp; ptrEvenList = &temp->next;} 
     } 

    *ptrOddList = NULL; 
    *ptrEvenList = NULL; 
} 

Answer 3

void split(ListNode *head,ListNode **ptrOddList,ListNode **ptrEvenList){ 
int remainder; 
int countO=0; 
int countE=0; 
ListNode *tempO,*tempE; 

if (head==NULL) 
    return; 
else{ 
    (*ptrOddList)=(struct node*)malloc(sizeof(ListNode)); 
    (*ptrEvenList)=(struct node*)malloc(sizeof(ListNode)); 

    while(head!=NULL){ 
     remainder=head->item%2; 

     if(remainder==0){ 
      if(countE>0){ 
       tempE->next=head; 
       tempE=tempE->next; 
      } 
          else 
           tempE=*ptrOddList; 
      tempE->item=head->item; 
      countE++; 

     } 
     else{ 
      if(countO>0){ 
       tempO->next=head; 
       tempO=tempO->next; 
      } 
          else 
           tempO=*ptrOddList; 
      tempO->item=head->item; 
      countO++; 

     } 
     head=head->next; 
    } 
    tempE->next=NULL; 
    tempO->next=NULL; 
    printf("Even List:"); 
    printNode((*ptrEvenList)); 
    printf("Odd List:"); 
    printNode((*ptrOddList)); 
} 
} 

Answer 4

Я думаю, что здесь речь идет разбить список на 2 половинки на основе индексов. Но я вижу реализации на values(item%2).

Итак, в списке первый узел должен иметь индекс 1 и второго узла 2 и так далее.

Используйте переменную count, которая первоначально устанавливает значение 0.

int node_count = 0; 
while(head != NULL) 
{ 
    node_count ++; 

    if(node_count%2) 
    { 
     //prepare odd_list; 
    } 
    else 
    { 
     //prepare even_list; 
    } 
    head = head->next; 
} 

Answer 5

void split(ListNode *head, ListNode **pOddList, ListNode **pEvenList) 
{ 
    int remainder; 
    ListNode *tmpO = NULL, *tmpE= NULL, *tmp; 

    if (head == NULL) 
    { 
     *pEvenList = NULL; 
     *pOddList = NULL; 
    } 
    else 
    { 
     tmp = head; 

     while (tmp != NULL) 
     { 
      remainder = tmp->item % 2; 

      if (remainder == 0) 
      { 
       if (tmpE == NULL) 
       { 
        tmpE = tmp; 
        tmp = tmp->next; 
        *pEvenList = tmpE; 
        tmpE->next = NULL; 
       } 
       else 
       { 
        tmpE->next = tmp; 
        tmp = tmp->next; 
        tmpE = tmpE->next; 
        tmpE->next = NULL; 
       } 
      } 
      else 
      { 
       if (tmpO == NULL) 
       { 
        tmpO = tmp; 
        tmp = tmp->next; 
        *pOddList = tmpO; 
        tmpO->next = NULL; 
       } 
       else 
       { 
        tmpO->next = tmp; 
        tmp = tmp->next; 
        tmpO = tmpO->next; 
        tmpO->next = NULL; 
       } 
      } 
     } 
    } 
}