算法 - c++ OJ出现段错误

Question

RT，我在做PAT的一道链表翻转题，本地调试没问题，但是提交一直出现段错误。十分不解，望各路神仙帮忙看看，先谢过了~

//
//  main.cpp
//  反转链表
//
//  Created by Jzzhou on 16/8/12.
//  Copyright © 2016年 Jzzhou. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;

struct Node {
    int addr;
    int data;
    int nextAddr;
    Node *next;
    void printNode() {
        if(nextAddr != -1) {
            printf("%.5d %d %.5d", addr, data, nextAddr);
        } else {
            printf("%.5d %d -1", addr, data);
        }
    }
};

int main(int argc, const char * argv[]) {
    int N, K, A;
    cin>>A>>N>>K;
    if (N == 0) {
        return 0;
    }
    Node nodes[100002];
    for (int i = 0; i < N; ++i) {
        int addr, data, nextAddr;
        cin>>addr>>data>>nextAddr;
        nodes[addr].addr = addr;
        nodes[addr].data = data;
        nodes[addr].nextAddr = nextAddr;
    }
    
    Node *head = &nodes[100001];
    if(nodes[A].addr != A) {
        return 0;
    }
    // 生成链表
    Node *temp = &nodes[A];
    head->next = temp;
    while (temp->nextAddr != -1) {
        temp->next = &nodes[temp->nextAddr];
        temp = temp->next;
    }
    temp->next = NULL;
    
    int time = N/K;
    // 链表翻转
    Node *tempHead = head;
    for (int i = 0; i < time; ++i)
    {
        Node *p1 = tempHead->next;
        for (int j = 0; j < K - 1; ++j)
        {
            Node *p2 = p1->next;
            p1->next = p2->next;
            p2->next = tempHead->next;
            tempHead->next = p2;
        }
        tempHead = p1;
    }
    // 输出链表
    Node *first = head->next;
    while (first != NULL) {
        first->printNode();
        first = first->next;
        if (first != NULL) {
            cout<<endl;
        }
    }
    
    return 0;
}

Answer 1

Ask you, there was no problem with your local compilation,,,, but my compilation was wrong.
1. You declared a Node array in the main function, with a size of 1e5+2. The stack space is small, and the array you declared is too large, causing stack overflow. It should be placed outside the main function. OK, global space.
2. I found that there is a problem with your code, QAQ. I have been looking for a segfault caused by the pointer accessing unapplied memory. I found that your code seems to have failed the sample

is not the same as standard output

There seems to be something wrong with your algorithm. . . . .

I finally found the pitfall! ! ! N不一定是链表的结点总数, so if you use N/K, you won’t get the correct number of times. There may be several linked lists in one data, and you need to get the 节点数
AC code for that linked list, which you changed above

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;

struct Node {
    int addr;
    int data;
    int nextAddr;
    Node *ne;
    void printNode() {
        if(nextAddr != -1) {
            printf("%05d %d %05d\n", addr, data, nextAddr);
        } else {
            printf("%05d %d -1\n", addr, data);
        }
    }
    Node(int a = -1, int b = -1, int c = -1, Node* d = NULL) : addr(a), data(b), nextAddr(c), ne(d) {}
};
Node nodes[100005];

int main(int argc, const char * argv[]) {
    int N, K, A;
    //freopen("D:\in", "r", stdin);
    //freopen("D:\out", "w", stdout);
    cin >> A >> N >> K;
    for (int i = 0; i < N; ++i) {
        int addr, data, nextAddr;
        cin>>addr>>data>>nextAddr;
        nodes[addr].addr = addr;
        nodes[addr].data = data;
        nodes[addr].nextAddr = nextAddr;
    }
    Node *head = &nodes[100001];
    //cout << head << endl;
    Node *temp = &nodes[A];
    head-> ne = temp;
    int cnt_n = 1;
    while (temp->nextAddr != -1 && temp) {
        temp-> ne = &nodes[temp->nextAddr];
        temp = temp->ne;
        ++cnt_n;
    }
    temp -> ne = NULL;
    Node* test = head;
    //cout << "linked list\n";
    //cout << test << endl;
    
    //while (test -> ne != NULL)
    //{
    //    printf("%05d\n",(test -> ne) -> nextAddr);
    //    test = test -> ne;
    //}
    
    int time = cnt_n/K;
    // 链表翻转
    Node *tempHead = head;
    for (int i = 1; i <= time; ++i)
    {
        Node *p1 = tempHead->ne;
        for (int j = 1; j <= K - 1; ++j)
        {
            Node *p2 = p1->ne;
            p1->ne = p2->ne;
            p1 -> nextAddr = p2 -> ne -> addr;
            p2->ne = tempHead->ne;
            p2 -> nextAddr = tempHead -> ne -> addr;
            tempHead->ne = p2;
            tempHead -> nextAddr = p2 -> addr;
        }
        tempHead = p1;
    }
    //cout << "linked list\n";
   // cout << test << endl;
    
    //test = head;
    //while (test -> next != NULL)
    //{
    //    printf("%05d\n",(test -> next) -> nextAddr);
    //    test = test -> next;
    //}
    
    // 输出链表
    // right code
    Node *first = head->ne;
    while (first  != NULL) {
        first->printNode();
        first = first->ne;
    }
    return 0;
}

Your original code also has some problems with the node exchange part. You only exchanged the next pointer without modifying the nextAddr in each Node.

Answer 2

After a brief look, assuming there is only one node, the following code may have errors:

// 链表翻转
Node *tempHead = head;
for (int i = 0; i < time; ++i)
{
    Node *p1 = tempHead->next;       // p1 指向链表中惟一一个节点
    for (int j = 0; j < K - 1; ++j)
    {
        Node *p2 = p1->next;         // p2 == NULL
        p1->next = p2->next;         // p2->next 报错
        p2->next = tempHead->next;
        tempHead->next = p2;
    }
    tempHead = p1;
}

It is recommended to track specific errors in a single step and see which line of execution the error is reported.

Also, I don’t understand what the following paragraph is about... Isn’t the judgment condition always false...

if(nodes[A].addr != A) {
    return 0;
}