判断两单链表是否相交



思路

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

• 如果相同，找出两链表之间长链和短链，长链表先行多出的长度（如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;