单链表被核心转储的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;
    }


  }

这是一道练习题 - HackerEarth 上的单链表第 1 题。代码编译正确，但运行进入运行时间错误，我无法弄清楚原因。

例如，如果列表是 {24, 18, 2, 5, 7, 16, 12} 返回的列表应该是 {2, 18 , 24 , 5 , 7 , 12 , 16}

应该反转链表中偶数编号的部分，使链表的其余部分保持不变。

此外，我对编程还很陌生，我是第一次学习数据结构和算法，所以请原谅这次任何糟糕的缩进和愚蠢的错误。我保证会变得更好。

Answer 1

将第 62 行更改为 - while(ptr != NULL && ptr->data % 2==0)

你应该先检查ptr != null条件，如果为假，那么ptr->data将不会因为短路评估而被执行。

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

虽然这会消除核心转储错误，但您不会获得所需的输出。你的代码也有逻辑错误。

Answer 2

您的代码中存在大量逻辑问题。首先，不需要分配 head 和 ptr。它们只是作为指向列表开头和结尾的指针（tail 是 ptr 的更具描述性的名称），例如

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

始终验证您的输入，至少是最低限度，例如

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

您唯一分配的时间是 temp 在值的读取循环中，例如

    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 个成员的一系列节点中第一个的指针。颠倒 node->data 个成员的顺序的逻辑都可以在列表的单次遍历中发生。

只需开始遍历您的列表即可。当遇到偶数节点时，保存指向该节点的指针并开始将数据推入堆栈。只要您的堆栈有值，当遇到奇数成员（或列表末尾）时，您只需从第二个指针指向的节点开始迭代，并使用堆栈中的 .top() 值作为其新值， .pop()边走边从你的堆栈中取出。当你的堆栈为空时——重复整个过程直到列表结束（不要忘记处理结束前的最后一组节点）

    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;
    }

剩下的就是输出修改后的列表并释放分配的内存（对于 hackerrank——您可以跳过释放内存）。根据需要调整输出格式：

    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';
}

例子Use/Output

使用问题中的数据作为输入，并输出原始列表和修改后的列表，您将：

$ ./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

检查一下，如果您还有其他问题，请告诉我。

单链表被核心转储的Hackerearth练习题代码

Code for the Hackerearth practice problem for singly linked list being core dumped

c++

stack

segmentation-fault

singly-linked-list