以下关于单向链表说法正确的是_

推荐

hehe丶

A.单链表的没个节点都具有唯一的前驱节点和唯一的后继节点，所以当两个单链表存在相交的节点时，这两个链表则同时拥有这个节点，以及这个节点的所有后继节点，当这个公共节点是尾节点时，他们则只含有公共一个节点-------尾节点。

B.快慢指针是判断单链表是否有环的一种方法：两个指针，每次移动的步长为2叫做快指针，每次移动步长为1的指针叫做慢指针。快慢指针同时从头结点出发，当快指针率先到达NULL的时候，则说明此单链表中不存在环，当快指针追上慢指针的时候，说明此单链表中存在环。

C.有环的单向链表和无环的单向链表不能相交，因为当相交的时候，无环的单向链表也会被迫存在一个环，只不过这个环的”起点“可能不是原来单向链表的头结点。

4.两个单向链表之间相交可以存在环。

编辑于 2016-08-11 09:15:15 回复(19)

打工不可能打工的

用纸写了一下

发表于 2018-07-17 16:15:16 回复(13)

跳跃的字母mosum

我记得这是微软一道面试编程题，给两个链表，判断其是否相交，主要考虑3个方面：

1.两个链表都为单链表，那么一旦相交意味着两个节点的next相同，之后的也都相同，所以尾节点也相同。

2.一个是单链表，一个是有环，那么就不可能存在相交的情况。这其中判断链表是否有环就是用的快慢指针法：设置两个指针，一个跳一格，一个跳两格(可以想象成环形跑道)，追上自然就有环了。

3.如果都是循环链表，遍历其中一个链表，直到找到与另一链表中某节点相同的节点就算是相交了。

这三方面也就回答了上述的选项，我觉得是ABC。

底下附上实现代码：

class Node{

private:

int data;

Node *next;

public:

Node(int _data){

data = _data;

next = NULL;

}

};

bool isJointSimple(Node*n1,Node*n2){

while(n1->next!=NULL){

n1=n1->next;

}

while(n2->next!=NULL){

n2=n2->next;

}

if (n1==n2)

{

return true;

}

else{

return false;

}

bool isJoint(Node*n1,Node*n2){

int a=hasRing(n1);

int b=hasRing(n2);

if (a+b==0)

{

return isJointSimple(n1,n2);

}

if (a+b==1)

{

return false;

}

if (a+b==2)

{

Node* temp=n1;

while(true){

if (temp==n2||temp->next==n2)

{

return true;

}

temp=temp->next->next;

n1=n1->next;

if (n1==temp)

{

return false;

}

int hasRing(Node *n){

Node*p1=n,*p2=n;

while(p2!=NULL&&p2->next!=NULL){

p1=p1->next;

p2=p2->next->next;

if (p1==p2)

{

return 1;

}

return 0;

}

编辑于 2016-08-12 00:19:16 回复(0)

lsyyzx

个人理解:单向链表包括无环与有环，如果单向链表相交，那么这两个链表要么都是有环，要么都是无环。

发表于 2017-04-04 13:33:01 回复(0)

sunlight_run

链表相交，要么都有环，要么都没有环

发表于 2017-06-12 10:58:17 回复(0)

Smoothing

1.注意两个链表相交不可能是X形状的，一定是Y形状的，因为单向链表（链表）任意节点只能有一个next,所以两个链表一旦相交就只能有一个尾节点。

2.同理，一个链表不可能出现6形状，有环链表的形状一定是O，所以有环链表和无环链表一定不能相交。

3.快慢指针是针对一个链表上同时运行两个指针，两个指针前进的速度不同，随时判断两个指针是否相等，如果相等说明有环。

4.单链表的性质是每个节点只能有一个后继和一个前驱，但是可能出现两个有环链表相交的情况。

发表于 2018-01-14 22:27:45 回复(3)

hxc

d求解如何俩单链表相交还能有环

发表于 2017-02-11 14:44:47 回复(1)

gycc

相交是什么意思

发表于 2021-11-21 20:27:55 回复(1)

TwinkleZheng

A.单链表的没个节点都具有唯一的前驱节点和唯一的后继节点，所以当两个单链表存在相交的节点时，这两个链表则同时拥有这个节点，以及这个节点的所有后继节点，当这个公共节点是尾节点时，他们则只含有公共一个节点-------尾节点。

B.快慢指针是判断单链表是否有环的一种方法：两个指针，每次移动的步长为2叫做快指针，每次移动步长为1的指针叫做慢指针。快慢指针同时从头结点出发，当快指针率先到达NULL的时候，则说明此单链表中不存在环，当快指针追上慢指针的时候，说明此单链表中存在环。

C.有环的单向链表和无环的单向链表不能相交，因为当相交的时候，无环的单向链表也会被迫存在一个环，只不过这个环的”起点“可能不是原来单向链表的头结点。

4.两个单向链表之间相交可以存在环。

发表于 2018-08-02 11:13:05 回复(0)

想找对象的突尼斯海怪这就开摆

相交的概念应是指两个链表具有相同的节点。

A选项个人认为单链表是单向的每个节点具有唯一前驱和唯一后继若两个链表相交，则一定具备公共的节点，这就意味着链表存在相同的部分，相同部分往后即可成为共同的尾节点。

B选项判定一个链表是否有环使用快慢指针法极其方便，并且两指针移动的步数为快慢指针的单步差值除链表总长度。

C选项这个选项我选错了但后来意识到了因为无环的单链表一旦与有环单链表相交意味着两者必具有相同的办法，就像黑格尔的哲学螺线一样，本来是条线，加入螺线后就有了环。

D选项链表相交可以有环相交也可以无环相交，所以D选项错误。

发表于 2022-05-26 20:53:10 回复(0)

CAM_DEV

A.单链表的没个节点都具有唯一的前驱节点和唯一的后继节点，所以当两个单链表存在相交的节点时，这两个链表则同时拥有这个节点，以及这个节点的所有后继节点，当这个公共节点是尾节点时，他们则只含有公共一个节点-------尾节点。 B.快慢指针是判断单链表是否有环的一种方法：两个指针，每次移动的步长为2叫做快指针，每次移动步长为1的指针叫做慢指针。快慢指针同时从头结点出发，当快指针率先到达NULL的时候，则说明此单链表中不存在环，当快指针追上慢指针的时候，说明此单链表中存在环。 C.有环的单向链表和无环的单向链表不能相交，因为当相交的时候，无环的单向链表也会被迫存在一个环，只不过这个环的”起点“可能不是原来单向链表的头结点。 4.两个单向链表之间相交可以存在环。

发表于 2021-03-10 23:40:34 回复(0)