判断两单链表是否相交

用户头像
石印掌纹
关注
发布于: 2020 年 07 月 29 日



思路

  • 如果两链表相交,最后节点一定相同。

  • 如果相同,找出两链表之间长链和短链,长链表先行多出的长度(如NodeA长度为4,NodeB长度为3,NodeA应该先走1步),然后同时遍历,判断当前指针找到的各自节点是否相同,如果相同返回相交节点。

  • 如果不同,说明不相交。



if (longNode == null || shortNode == null) {

return null;

}

Node node = new Node();

Node node1 = new Node();

int nodeCursor = 0;

int nodeCursor1 = 0;

Node longNode = node;

Node shortNode = node1;



while(longNode.next() != null) {

nodeCursor++;

longNode = longNode.next();

}

while(shortNode.next() != null) {

nodeCursor1++;

shortNode = shortNode.next();

}



// 尾节点相等说明两个链表相交

if (shortNode == longNode) {

// 找出长、短链表

if (nodeCursor > nodeCursor1) {

longNode = node;

shortNode = node1;

} else {

longNode = node1;

shortNode = node;

}

// 长链表先行

for(int i = 0; i < Math.abs(nodeCursor - nodeCursor1); i++) {

longNode = longNode.next();

}

while (longNode != null && shortNode != null) {

if (longNode == shortNode){

return longNode;

}

longNode = longNode.next();

shortNode = shortNode.next();

}

} else {

// 说明两链表不相交

}

return null;

用户头像

石印掌纹

关注

还未添加个人签名 2018.11.22 加入

还未添加个人简介

评论

发布
暂无评论
判断两单链表是否相交