永发信息网

生成单链表怎么会出现环

答案:2  悬赏:10  手机版
解决时间 2021-04-29 14:32
链表节点的结构体:

struct graphNode{
int id; //ver id
graphNode *next;

graphNode(){ id = -1; next = NULL; }
graphNode(int i){ id = i; next = NULL; }
};

链表:
graphNode *loopList = new graphNode();
然后按序插入节点:
graphNode *tmp2;

tmp2 = loopList->next;
loopList->next= new graphNode(tmp->id); (从其他地方来的id)
loopList->next->next = tmp2;

这里出现一个奇怪的情况。在链表开头,节点id是271,然后插入了13个不一样的节点,然后又插入一个节点id是271,然后我用while遍历:(主要是想检测新加入的节点序列在该序列中是否出现过)

graphNode *t = loopList->next;
while (t != NULL)
{
fo << "loop id:" << t->id << endl;
if ((t->id) = (tmp->id))
{
if ((tmp->next == NULL) || (t->next == NULL))break;
if ((t->next->id) == (tmp->next->id))
{
loopFlag = -1;
break;
}
}
t = t->next;
}
delete t;
结果发现两个id为271的节点连起来了变成一个,使链表变成一个环,while出不来了。。。
求看看是什么情况><
最佳答案
这个看起来比较奇特,但是只有结构体中是允许这样子做的;
还有一种形式,不过同样你也未必能接受,如下:

typedef int ElementType;
typedef struct ListNode *List;

struct ListNode
{
ElementType data;
List next;
};
全部回答
s = x + y 2s = nr + s(假设环的周长为r,在相遇前快指针走了n圈) 由公式2推导出s = nr,带入公式1得到nr = x + y === x = nr -y; 现在再设两个指针p1、p2,步长均为1,p1从单链表起点开始遍历,p2从相遇点开始遍历(相遇点可以得到),根据公式x=nr-y,当p1移动x步时(移动到了入口处),p2移动了nr-y步,由于p2是从相遇点开始遍历的,故nr表示又回到了相遇点,-y表示倒退y步(表示入口点到相遇点的距离),由此可以得到p1和p2是同时到达入口点的。 故算法可以写为:
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
还是梦幻西游号问价
小品车站奇遇全部台词,2015春晚小品《车站奇
当你站在生命的十字路口时你会犹豫吗
花瓣浴的做法
手机可以改装吗?
成绩能证明一个人的付出吗?
最好的朋友 为什么她会这样?
09年10月或11月有什么诺基亚新款手机吗?
有哪些好听的。带点悲伤的歌啊?
QQ被挂马了怎么办?
石磊:维修摩托车电动车地址有知道的么?有点
一道初三物理简单机械问题
2手电脑估价
手机千牛怎么发送链接,手机上怎么复制店铺链
神舟战神K680E-G6D1 15.6英寸游戏笔记本电脑
推荐资讯
我和僵尸有个约会3上还是原班人马么 ?
谁有异次元杀阵的avi格式下载地址阿 ??
什么牌子的牛仔裤好穿,有弹性的牛仔裤和没有
求没有如果的简谱
怎样树立人生目标
广发信用卡透支现金5000.到期还款日还了4500
这几个版本的gta哪个更值得玩
风暴英雄怎么添加好友,风暴英雄怎么和好友一
飞利浦X503多少钱
NOKIA3100手机的游戏下载关卡时怎么总是失败
团包梁在哪里啊,我有事要去这个地方
质量控制措施有哪些,项目质量控制的方法工具
正方形一边上任一点到这个正方形两条对角线的
阴历怎么看 ?