两个链表公共子节点问题

提示：大家都在做什么？ 不做什么。就是等夏天结束

---

---

前言

提示：会持续量个月，每周至少写两篇博客🤩：

题目：

这是一道非常经典的链表题目，也属于常考的问题。
已知：

1. 两个链表
2. 找到相交点

注意：

1. 如果两个链表没有交点，返回 null.
2. 在返回结果后，两个链表仍须保持原有的结构。
3. 可假定整个链表结构中没有循环。 程序尽量满足 O(n)
4. 时间复杂度，且仅用 O(1) 内存。

好了题目都说好了，那我们就开始冲吧💕

提供四种解决方法的思路：

1. 哈希表或集合实现 ⭐
2. 使用栈确定实现 ⭐⭐
3. 拼接字符串实现 ⭐⭐⭐
4. 和差双指针实现 ⭐⭐⭐⭐⭐

拿到题目要怎么思考：审题

单链表的结构：

链表中的元素以节点的形式进行存储，每个节点都包含了数据和指向下一个节点的引用。
注意一句话：链表中的每个节点只能指向下一个节点，但是可以又多个指针指向同一个节点。【eg:C1节点】
当然如果不知道入手的话：就从头开始想一想常见的数据结构和常见的算法思想
常见的数据结构：
数组、链表、队列、栈、Hash、集合、树、堆。
常见的算法思想：
查找、排序、双指针、递归、迭代、分治、贪心、回溯、动态规划等。
按照这个思绪走下去：

1. 蛮力呗
   就用遍历（冒泡的思想，一个一个比较）用第一个链表的第一个元素一次和第二个链表的元素作比较，最终找到相同的公共子节点，但是这样的效率太低了【O(N2)】 复杂 排除💣
2. Hash求解
   当然是把第一个链表的所有元素放道一个Map中，然后需要遍历一遍第二个链表，顺便检测一下是否存在在Hash中，如果存在的话，就找到相同的公共子节点。【这不就可以了吗？❤️，当然了用集合也是不错了：这不又一种方法⭐】
3. 队和栈试试呗
   队列的话？感觉不太行哈😂。那如果用栈的话，想一想要怎么实现呢？（思考3分钟）
   采用两个栈，分别将链表的元素压入栈中，然后便出栈，边比较元素是否相同。如果相同说明有公共子节点，那么最晚出现的一组相同的节点就是相交的（公共子节点🥰找到了）

梳理完整之后：
（面试小技巧）通过上面的思考，可以直接和面试官说应该可以采用HashMap做，当然使用集合和栈也是可以的。
期待接下来的面试官往下提问。（然后你就可以谈谈具体是怎么解决的）
当然如果你第一次说错了也没关系的，后面发现问题，直接和面试关说就可以。（注意面试是需要交流的过程，如果有疑问，可以提出来）
以下是一些比较经典的解法：

哈希表或集合实现

思路：将第一个链表遍历存入Map中，然后再遍历另一个链表，一边遍历，一边检测是否存在相同的元素，如果存在节点一定可以检测出来。【当然 使用集合的话也是这样的】

/*** 方法1：通过Hash辅助查找** @param pHead1* @param pHead2* @return*/
public static ListNode findFirstCommonNodeByMap(ListNode pHead1, ListNode pHead2) {// 检测参数if (pHead1 == null || pHead2 == null){return null;}// 保存头节点ListNode cur1 = pHead1;ListNode cur2 = pHead2;// 创建一个map 用节点做key   数据做val  ？？HashMap<ListNode, Integer> hashMap = new HashMap<>();// 将所有元素存入map中while(cur1 != null){hashMap.put(cur1,cur1.val);cur1 = cur1.next;}// 遍历第二个链表while(cur2 != null){// 如果存在就直接返回公共子节点if (hashMap.containsKey(cur2)){return cur2;}cur2 = cur2.next;}return null;
}

/*** 方法2：通过集合来辅助查找** @param headA* @param headB* @return*/
public static ListNode findFirstCommonNodeBySet(ListNode headA, ListNode headB) {// 集合这里可以想到的set啦🤩（毕竟是存在重复特性的）// 先判断参数  set 不能直接用set 需要使用hashsetSet<ListNode> set = new HashSet<>();// 遍历一个链表 将他存入set集合中while (headA != null) {set.add(headA);headA = headA.next;}// 遍历第二个链表找出 相同的节点while (headB != null) {//  if (!set.add(headB)){//      return headB;//  }  利用set特性if(set.contains(headB)){return headB;}headB = headB.next;}return null;}

使用栈来实现

思路：这里采用两个栈，分别将两个链表存入栈中，然后一边出栈，一边比较，找到最晚出栈的那一组就是这两个链表的公共子节点。不废话了直接上代码😂【冲】

/*** 方法3：通过栈*/
public static ListNode findFirstCommonNodeByStack(ListNode headA, ListNode headB) {// 参数校验/* if(headA == null || headB == null){return null;}*/// 创建连个栈Stack<ListNode> stack1 = new Stack();Stack<ListNode> stack2 = new Stack();// 分别存储两个链表while(headA != null){   // 这里参数校验过  前面的校验就可以省掉stack1.push(headA);headA = headA.next;}while (headB != null){stack2.push(headB);headB = headB.next;}// 出栈 遍历 找到目标ListNode ans = null;while (stack1.size() > 0 && stack2.size() > 0){if (stack1.peek() == stack2.peek()){ans = stack1.pop();stack2.pop();}else {break;}}return ans;
}

拼接字符串实现 (组合在一起）

思路：（也可叫做双指针）
首先我我们先看两个链表：

以分叉点拆分：
组合在一起（连接）

从次可以看出 4 开始两个链表就是一样的了，也就是说公共子节点是 4
当然了，如果创建新的链表的话就太浪费时间了，我们可以等链表结束后，调整从下一个链表开始，这样的话思路就来了吧😃，那我就开始装逼了【哈哈】

/*** 方法4：通过序列拼接*/
public static ListNode findFirstCommonNodeByCombine(ListNode pHead1, ListNode pHead2) {// 参数检验if (pHead1 == null || pHead2 == null) {return null;}// 保留头节点ListNode p1 = pHead1;ListNode p2 = pHead2;while(p1 != p2){p1 = p1.next;p2 = p2.next;if (p1 != p2){ // 注意这里if (p1 == null){p1 = pHead2;}if (p2 == null){p2 = pHead1;}}}return p1;}

注意：
if (p1 != p2){ //注意这里 避免死循环【没有公共子节点的情况】

和差双指针实现

思路：
字面意思看是需要使用差和的双指针来解决。具体来说

1. 分别计算出每个链表的长度 L1 L2
2. 长的链表先走| L1 - L2 |
3. 同时遍历，找到第一个相同的节点

话不多说，那就上代码吧🌰

/*** 方法5：通过差值来实现** @param pHead1* @param pHead2* @return*/
public static ListNode findFirstCommonNodeBySub(ListNode pHead1, ListNode pHead2) {// 参数检验if (pHead1 == null || pHead2 == null) {return null;}// 保留头节点ListNode p1 = pHead1;ListNode p2 = pHead2;int l1 = 0;while(p1 != null){p1 = p1.next;l1++;}int l2 = 0;while(p2 != null){p2 = p2.next;l2++;}// 计算出先走的步数int sub = l1 > l2 ? l1 - l2 : l2 - l1;p1 = pHead1;p2 = pHead2;if(l1 > l2){int temp = 0;while(temp < sub){p1 = p1.next; // 此时 p1 已经改变了  所以需要上面的从新复值temp++;}}if(l1 < l2){int temp = 0;while(temp < sub){p2 = p2.next;temp++;}}while (p1 != p2){ // 这里不能用ifp1 = p1.next;p2 = p2.next;}return p1;}

---

总结

提示：思考的方式很重要 建立习惯