剑指Offer（三十六）-- 两个链表的第一个公共节点
代码已经同步到 刷题仓库：CodeSolution 仓库地址：https://github.com/Damaer/CodeSolution 文档地址：https://damaer.github.io/CodeSolution/
题目描述
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
思路以及解答
HashSet是否包含
第一种做法，直接依赖于HashSet，遍历第一个链表的时候，将所有的节点，添加到hashset中，遍历第二个链表的时候直接判断是否包含即可，属于空间换时间的做法。
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//创建集合set
Set<ListNode> set = new HashSet<>();
while (pHead1 != null) {
set.add(pHead1);
pHead1 = pHead1.next;
}
while (pHead2 != null) {
if (set.contains(pHead2))
return pHead2;
pHead2 = pHead2.next;
}
return null;
}
计算个数提前移动差值
譬如现在有一个链表1->2->3->6->7，另外一个链表4->5->6->7,明显可以看出第一个公共节点是 6 。
最直接的方法，每一个链表都遍历一次，计算链表中的个数，比如1->2->3->6->7个数为5，4->5->6->7个数为4，两者相差1（设为k）个。
我们可以使用两个指针，分别指向链表的头部。然后让第一个链表的指针先走k=1步。
这样就相当于指针后面的两个链表等长了。
就可以开始比较，如果不相等，则两个指针都往后移动即可，知道节点为null。
代码如下：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
// 只要有一个为空，就不存在共同节点
if (pHead1 == null || pHead2 == null) {
return null;
}
// 计算链表1中的节点个数
int numOfListNode1 = 0;
ListNode head1 = pHead1;
while (head1 != null) {
numOfListNode1++;
head1 = head1.next;
}
// 计算链表2中节点个数
int numOfListNode2 = 0;
ListNode head2 = pHead1;
while (head2 != null) {
numOfListNode2++;
head2 = head2.next;
}
// 比较两个链表的长度
int step = numOfListNode1 - numOfListNode2;
if (step > 0) {
// 链表1更长，链表1移动
while (step != 0) {
pHead1 = pHead1.next;
step--;
}
} else {
// 链表2更长，链表2移动
while (step != 0) {
pHead2 = pHead2.next;
step++;
}
}
// 循环遍历后面的节点，相等则返回
while (pHead1 != null && pHead2 != null) {
if (pHead1 == pHead2) {
return pHead1;
} else {
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
}
return null;
}
}
但是上面的做法，如果公共节点在最后一个，假设一个链表长度为n，一个为m，那么计算个数就要全部遍历，需要n+m。两个链表都移动，到最后一个节点的时候才相等，也是n +m，也就是O(2*(n+m))。
拼接链表
有没有更加好用的做法呢？肯定有，我们来看：两个链表分别是：
如果我在第一个链表后面拼接上第二个链表，第二个链表后面拼接上第一个链表，就会变成下面的样子：
发现了一个规律，也就是拼接之后的链表，是等长度的，第一个和第二个链表都从第一个开始比较，只要相等，就说明是第一个公共节点。也就是上面被圈起来的6节点。
代码如下：
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
// 只要有一个为空，就不存在共同节点
if (pHead1 == null || pHead2 == null) {
return null;
}
ListNode head1 = pHead1;
ListNode head2 = pHead2;
while (head1 !=head2) {
// 如果下一个节点为空，则切换到另一个链表的头节点，否则下一个节点
head1 = (head1 == null) ? pHead2 : head1.next;
head2 = (head2 == null) ? pHead1 : head2.next;
}
return head1;
}
}
【作者简介】：秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。
此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者核实删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~ - END -
腾讯云开发者
