Код для проблемы практики Hackerearth для односвязного списка, сбрасываемого ядром

Question

    #include <iostream>
    #include<vector>
    #include <stack>
    using namespace std;

    class Node
    {
    public:
    int data;
    Node* next;
    };

    int main()
    {
    int n;
    cin >> n;
    Node* head = new Node;
    Node* ptr = new Node;
    head = NULL;
    // take the input for the linked list;

    for (int i = 0; i< n ;i++)
    {
        int num;
        cin >> num;
        Node* temp = new Node;
        temp->data = num;
        temp->next = NULL;
        if(head == NULL)
        {
            head = temp;
            //head->next = NULL;
            ptr = head;
        }
        else
        {
           ptr->next = temp;
           ptr = temp;
        }

        // linked list made
     }
    Node* head1 = new Node;
    head1 = head;

    //ptr->data = NULL;
    //ptr->next = NULL;

    stack <int> stk;
    ptr = head1;

    while(ptr != NULL)
    {
        if(head1->data % 2 != 0)
        {
            head1 = head1->next;
        }

        else
        {
            ptr = head1;
            while(ptr->data % 2==0 && ptr != NULL)
            {
                stk.push(ptr->data);
                ptr = ptr->next;
            }

            while(head1 != ptr)
            {
            int n ;
            n = stk.top();
            head1->data = n;
            head1 = head1->next;
            stk.pop();
            }

        }
       //head1 = ptr;
        // replace the values again in the linked list
    }

    // print the linked list

    while(head != NULL)
    {
        cout << head->data << " ";
        head = head->next;
    }


  }

Это практическая проблема - 1 для односвязного списка на HackerEarth. Код компилируется правильно, но сталкивается с ошибкой во время выполнения, и я не могу понять, почему.

Например, если список {24, 18, 2, 5, 7, 16, 12} Возвращаемый список должен быть {2, 18, 24, 5, 7, 12, 16}

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

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

Answer 1

В вашем коде большое количество проблем с логи c. Для начала, head и ptr не должны быть выделены. Они просто служат указателями на начало и конец вашего списка (tail было бы более описательным именем для ptr), например,

    Node *head = nullptr, *tail = nullptr;  /* don't allocate */

Всегда проверяйте ввод, по крайней мере, минимально, например

    if (!(cin >> n))                        /* validate every input */
        return 1;

Единственное время, которое вы выделяете для temp в считанном l oop значений, например,

    for (int i = 0; i < n; i++) {           /* loop n times */
        int num;

        if (!(cin >> num))                  /* read/validate int input */
            return 1;

        Node *temp = new Node;              /* allocate new node */
        temp->data = num;                   /* initialize data & next */
        temp->next = nullptr;

        if (head == nullptr)                /* if 1st in list */
            head = tail = temp;             /* set head/tail to temp */
        else {
            tail->next = temp;              /* otherwise add at tail */
            tail = temp;
        }
    }

Вы можете либо повторно использовать указатель tail, либо просто объявить второй указатель для сохранения указателя на первый в серии узлов с четными node->data членами. Логика c для изменения последовательности даже node->data членов может происходить в пределах одного обхода списка.

Просто начните обходить свой список. Когда встречается четный узел, сохраните указатель на узел и начните помещать данные в ваш стек. Когда встречается нечетный член (или конец списка), пока в вашем стеке есть значения, вы просто выполняете итерацию, начиная с узла, на который указывает ваш второй указатель, и используете значение .top() из стека в качестве его нового значения, .pop() Из вашего стека, как вы go. Когда ваш стек пуст - повторяйте весь процесс до конца списка (не забудьте обработать последний набор узлов до конца)

    stack<int> stk {};                      /* declare stk & 2nd pointer */
    Node *iter2 = nullptr;
    for (Node *iter = head; iter; iter = iter->next)    /* iterate nodes */
        if (iter->data % 2 == 0) {          /* if even data */
            stk.push (iter->data);          /* add to stk */
            if (!iter2)                     /* if 2nd iter nullptr */
                iter2 = iter;               /* set to current node */
        }
        else if (iter2 && !stk.empty()) {   /* if odd data */
            /* loop while stk not empty and 2nd iter not nullptr */
            for (; !stk.empty() && iter2; stk.pop()) {
                iter2->data = stk.top();    /* pop from stk to node */
                iter2 = iter2->next;        /* advance 2nd iter */
            }
            iter2 = nullptr;                /* set to nullptr at end */
        }

для обработки последних узлов в списке:

    /* update final nodes in list */
    for (; !stk.empty() && iter2; stk.pop()) {
        iter2->data = stk.top();
        iter2 = iter2->next;
    }

Осталось только вывести измененный список и освободить выделенную память (для хакерранка - вы можете пропустить освобождение памяти). Настройте выходной формат по своему усмотрению:

    cout << "modified: ";                   /* output modified list */
    for (Node *iter = head; iter;) {        /* iterate over list */
        cout << " " << iter->data;          /* output values */
        Node *victim = iter;                /* save poiter to node */
        iter = iter->next;                  /* advance to next */
        delete victim;                      /* delete victim */
    }
    cout << '\n';

Собрав его в целом, вы можете сделать:

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Node {
  public:
    int data;
    Node *next;
};

int main ()
{
    int n;
    Node *head = nullptr, *tail = nullptr;  /* don't allocate */

    if (!(cin >> n))                        /* validate every input */
        return 1;

    for (int i = 0; i < n; i++) {           /* loop n times */
        int num;

        if (!(cin >> num))                  /* read/validate int input */
            return 1;

        Node *temp = new Node;              /* allocate new node */
        temp->data = num;                   /* initialize data & next */
        temp->next = nullptr;

        if (head == nullptr)                /* if 1st in list */
            head = tail = temp;             /* set head/tail to temp */
        else {
            tail->next = temp;              /* otherwise add at tail */
            tail = temp;
        }
    }

    cout << "original: ";                   /* output original list */
    for (Node *iter = head; iter; iter = iter->next)
        cout << " " << iter->data;
    cout << '\n';

    stack<int> stk {};                      /* declare stk & 2nd pointer */
    Node *iter2 = nullptr;
    for (Node *iter = head; iter; iter = iter->next)    /* iterate nodes */
        if (iter->data % 2 == 0) {          /* if even data */
            stk.push (iter->data);          /* add to stk */
            if (!iter2)                     /* if 2nd iter nullptr */
                iter2 = iter;               /* set to current node */
        }
        else if (iter2 && !stk.empty()) {   /* if odd data */
            /* loop while stk not empty and 2nd iter not nullptr */
            for (; !stk.empty() && iter2; stk.pop()) {
                iter2->data = stk.top();    /* pop from stk to node */
                iter2 = iter2->next;        /* advance 2nd iter */
            }
            iter2 = nullptr;                /* set to nullptr at end */
        }
    /* update final nodes in list */
    for (; !stk.empty() && iter2; stk.pop()) {
        iter2->data = stk.top();
        iter2 = iter2->next;
    }

    cout << "modified: ";                   /* output modified list */
    for (Node *iter = head; iter;) {        /* iterate over list */
        cout << " " << iter->data;          /* output values */
        Node *victim = iter;                /* save poiter to node */
        iter = iter->next;                  /* advance to next */
        delete victim;                      /* delete victim */
    }
    cout << '\n';
}

Пример Использование / Вывод

Использование Ваши данные из вашего вопроса в качестве входных данных и вывода как исходного, так и измененного списков, вы должны иметь:

$ ./bin/hrll
7 24 18 2 5 7 16 12
original:  24 18 2 5 7 16 12
modified:  2 18 24 5 7 12 16

Просмотрите вещи и дайте мне знать, если у вас есть дополнительные вопросы.

Answer 2

Измените номер строки 62 следующим образом - while(ptr != NULL && ptr->data % 2==0)

Сначала следует проверить условие ptr != null, если оно ложно, то ptr->data не будет выполнено из-за оценки короткого замыкания.

https://en.wikipedia.org/wiki/Short-circuit_evaluation

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