2020-01-09：如何判断单链表交叉？
MoJieBlog opened this issue · 9 comments
先有A，B两个链表。A，B同时开始遍历。从A开始遍历，遍历至A链表尾部时转移至B链表开头。从B开始遍历，遍历至B链表尾部时转移至A开头。这样，两个指针相一致处非空即为交叉链表。
如果两个链表相交的话，则它们的尾结点一定是相同的，呈横向的“Y”字型，那么最简单的方式就是分别遍历两个链表到结尾，对比结尾的值是否相等就可以了
如果两个链表相交的话，则它们的尾结点一定是相同的，呈横向的“Y”字型，那么最简单的方式就是分别遍历两个链表到结尾，对比结尾的值是否相等就可以了
正解。
题意不清晰：
1，若两个单链表，则若有相交，则末尾节点相同
2，若单链表内部交叉，则判断单链表，是否为循环链表
如果两个链表相交的话，则它们的尾结点一定是相同的，呈横向的“Y”字型，那么最简单的方式就是分别遍历两个链表到结尾，对比结尾的值是否相等就可以了
正解。
不赞同。 如果A链表的末尾结点 与 B链表的头结点相交的话，“对比结尾的值是否相等”就不成立了。
如果两个链表相交的话，则它们的尾结点一定是相同的，呈横向的“Y”字型，那么最简单的方式就是分别遍历两个链表到结尾，对比结尾的值是否相等就可以了
正解。
不赞同。 如果A链表的末尾结点 与 B链表的头结点相交的话，“对比结尾的值是否相等”就不成立了。
A链表的末尾节点和B链表的头结点相交，则要么B结点就一个，要么就是A的末尾结点不是真的末尾结点。。。不如，A肯定会继续B的往下面走。
这个题应该是问假如两个单键表相交，请找出相交的位置的节点。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode currA = headA;
ListNode currB = headB;
int lengthA = 0;
int lengthB = 0;
// 让长的先走到剩余长度和短的一样
while (currA != null) {
currA = currA.next;
lengthA++;
}
while (currB != null) {
currB = currB.next;
lengthB++;
}
currA = headA;
currB = headB;
while (lengthA > lengthB) {
currA = currA.next;
lengthA--;
}
while (lengthB > lengthA) {
currB = currB.next;
lengthB--;
}
// 然后同时走到第一个相同的地方
while (currA != currB) {
currA = currA.next;
currB = currB.next;
}
// 返回交叉开始的节点
return currA;
}
如果两个链表相交的话，则它们的尾结点一定是相同的，呈横向的“Y”字型，那么最简单的方式就是分别遍历两个链表到结尾，对比结尾的值是否相等就可以了
为什么两链表相交 则尾节点相同？A，B两链表不能走出“X”字型吗
如果两个链表相交的话，则它们的尾结点一定是相同的，呈横向的“Y”字型，那么最简单的方式就是分别遍历两个链表到结尾，对比结尾的值是否相等就可以了
是不是交叉点意味着内存地址相同？如果这样就能解释一定是Y字型