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;
}
题主你本地编译居然没有问题,,,,我编译就错。
![](http://img.php.cn/upload/image/000/000/000/6f2ae6fe7601a99063e4e321223e24cc-0.png)
1.题主你在main函数里面声明了一个Node数组,大小为
1e5+2
,栈的空间较小,而你声明的数组过大,导致了栈溢出,应该放在main函数外面才行,全局空间。2.发现题主你代码有问题啊,QAQ,还一直在找是不是指针访问了未申请的内存的原因导致的段错误,发现你代码好像样例都没过
和标准输出不一样
你的算法好像有点问题。。。。。
我终于找到坑点了!!!
N不一定是链表的结点总数
, 所以你用N/K,得不到正确的次数,可能有几条链表一个数据里面,要针对那条链表获得节点数
AC代码,在你的上面改的
你原来的代码,交换节点部分也有点问题,你只是交换了next指针,而没有修改每个Node里面的nextAddr。
大概看了一下,假设只有一个节点时,下面这段代码可能出现错误:
具体错误建议单步跟踪,看执行到哪一行报错。
另外下面这段要干嘛没看懂……判断条件难道不是永远为假么……