JZ52 两个链表的第一个公共结点
JZ52 两个链表的第一个公共结点
描述
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
数据范围：n ≤ 1000；
要求：空间复杂度O(1)，时间复杂度O(n)。
示例1
输入：
{1,2,3},{4,5},{6,7}
返回值：
{6,7}
说明：第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分，这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的。
示例2
输入：
{1},{2,3},{}
返回值：
{}
说明：2个链表没有公共节点 ,返回null，后台打印{}
解析
由于要求空间复杂度O(1)，时间复杂度O(n)，则如遍历两个链表的所有节点（时间复杂度O(n2) ）、利用栈装入两个链表再从尾部开始找（空间复杂度O(1) ）的方法都不符合要求。这里使用两种稍微偏数学一点的方法解决。
差值法
由于两个链表不一定等长，所以不能直接在两个链表从头进行同步遍历时进行比较，不过由此可以产生一种思路：让长的链表先走 n 步，其中 n 为长链表比短链表多出的节点数，使得他们长度相等，再进行同步遍历比较。
代码清单
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode node1 = pHead1;
ListNode node2 = pHead2;
int num1 = 0, num2 = 0;
// 先求两个链表的长度
while(node1 != null){
num1++;
node1 = node1.next;
}
while(node2 != null){
num2++;
node2 = node2.next;
}
// 长的先把多余部分走了
int sub = 0;
ListNode temp = null, temp2 = null;
if(num1 > num2){
sub = num1 - num2;
temp = pHead1;
temp2 = pHead2;
}else{
sub = num2 - num1;
temp = pHead2;
temp2 = pHead1;
}
while(sub != 0){
temp = temp.next;
sub--;
}
// 长度相同了，一起走进行对比即可
while( temp != null && temp2 != null){
if( temp == temp2)
return temp;
temp = temp.next;
temp2 = temp2.next;
}
return null;
}
}
这种方式思路简单，但实现时的步骤比较复杂，下面换一种实现更简单的方法。
等值法
由于比较时的关键在于两个链表长度不一定相等，所以我们可以采取操作使两个链表的长度相等。
如果有公共部分
设链表1的特有部分的长度为 A，公共部分长度为 C，链表2的特有部分长度为 B，公共部分长度也是 C。
首先 ，将链表1与链表2组合起来，作为链表 a，将链表2与链表1组合起来，作为链表 b。
可以知道链表 a 和 b 的长度是相同的，所以A + C + B + C = B + C + A + C 成立。同时可以发现，在遍历完 A C B 和 B C A 后，两个链表已经经过相同的长度，接下来他们都将遍历到相同部分 C 的头结点，也就是说，只要进行链表 a 和 b 的遍历，就能让遍历指针同步到达公共部分的头节点，此时两个遍历指针相同，这就是我们要找的返回值。
如果没有公共部分
即链表1的特有部分为 A 和 C，链表2的特有部分为 B 和 D，同样将它们组合为链表 a 和 b。
则进行链表 a 和 b 的遍历时，有 A + C + B + D = B + D + A + C 成立，也就是说，遍历完链表 a 和 b 后，遍历指针会同时指向空。此时它们同时为空，符合相同的条件，对应的返回值也为 null，即不存在公共部分。
若两链表长度相同也是符合这个规律的，不过是 1+2=3 与 2+1=3 和 1+1=2 与 1+1=2 的区别罢了。
代码清单
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode node1 = pHead1;
ListNode node2 = pHead2;
// 循环到两个指针相同为止
// 找到相同的就停在相同的，找不到最后会同时到空（无论长度是否相等）
while(node1 != node2){
// 链表1走完了就继续走链表2
if(node1 != null )
node1 = node1.next;
else
node1 = pHead2;
// 链表2走完了就继续走链表1
if(node2 != null )
node2 = node2.next;
else
node2 = pHead1;
}
return node1;
}
}
总结
由于本题限制了时间复杂度和空间复杂度，所以需要采用巧妙一点的方法，不然直接暴力破解或者借助其他数据结构也能完成（= =），不过多看点巧妙的方法也是挺好的。
从写完这题到完成这篇笔记用了3天，属实够摸。