剑指offer-36、两个链表的第⼀个公共节点

题⽬描述

输⼊两个链表，找出它们的第⼀个公共结点。（注意因为传⼊数据是链表，所以错误测试数据的提示是⽤其他⽅式显示的，保证传⼊数据是正确的）
思路及解答

HashSet包含法

第⼀种做法，直接依赖于 HashSet ，遍历第⼀个链表的时候，将所有的节点，添加到 hashset 中，
遍历第⼆个链表的时候直接判断是否包含即可，属于空间换时间的做法。

1. public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
2.         if (pHead1 == null || pHead2 == null) return null;
3.         
4.         // 使用HashSet存储第一个链表的所有节点
5.         HashSet<ListNode> visited = new HashSet<>();
6.         
7.         // 遍历第一个链表，将所有节点加入集合
8.         ListNode current = pHead1;
9.         while (current != null) {
10.             visited.add(current);
11.             current = current.next;
12.         }
13.         
14.         // 遍历第二个链表，检查节点是否在集合中
15.         current = pHead2;
16.         while (current != null) {
17.             if (visited.contains(current)) {
18.                 return current; // 找到第一个公共节点
19.             }
20.             current = current.next;
21.         }
22.         
23.         return null; // 没有公共节点
24.     }

复制代码

• ​时间复杂度​：O(m+n)，需要遍历两个链表各一次
  
• ​空间复杂度​：O(min(m,n))，存储较短链表的节点
  

双栈法

利用栈的后进先出特性，从链表尾部开始比较，找到最后一个相同的节点。公共节点之后的节点都是相同的，所以从后往前比较，最后一个相同的节点就是第一个公共节点

1. import java.util.Stack;
3. public class Solution {
4.     /**
5.      * 使用双栈查找两个链表的第一个公共节点
6.      * 思路：将两个链表分别压入栈中，然后同时出栈比较
7.      * 时间复杂度：O(m+n)，空间复杂度：O(m+n)
8.      */
9.     public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
10.         if (pHead1 == null || pHead2 == null) return null;
11.         
12.         Stack<ListNode> stack1 = new Stack<>();
13.         Stack<ListNode> stack2 = new Stack<>();
14.         
15.         // 将两个链表的所有节点分别压入栈中
16.         ListNode current = pHead1;
17.         while (current != null) {
18.             stack1.push(current);
19.             current = current.next;
20.         }
21.         
22.         current = pHead2;
23.         while (current != null) {
24.             stack2.push(current);
25.             current = current.next;
26.         }
27.         
28.         ListNode commonNode = null;
29.         
30.         // 同时从两个栈弹出节点进行比较
31.         while (!stack1.isEmpty() && !stack2.isEmpty()) {
32.             ListNode node1 = stack1.pop();
33.             ListNode node2 = stack2.pop();
34.             
35.             if (node1 == node2) {
36.                 commonNode = node1; // 记录公共节点
37.             } else {
38.                 break; // 遇到不同节点，停止比较
39.             }
40.         }
41.         
42.         return commonNode;
43.     }
44. }

复制代码

• 时间复杂度​：O(m+n)，需要遍历两个链表各两次（压栈和出栈）
  
• ​空间复杂度​：O(m+n)，需要两个栈存储所有节点
  

长度差法（推荐）

可以将两个链表想象为两段路程，公共节点是终点。让长的链表先走多出的距离，然后同时前进，就能同时到达公共节点
譬如现在有⼀个链表 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。

1. /*
2. public class ListNode {
3. int val;
4. ListNode next = null;
5. ListNode(int val) {
6. this.val = val;
7. }
8. }*/
9. public class Solution {
10.      public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
11.          // 只要有⼀个为空，就不存在共同节点
12.          if (pHead1 == null || pHead2 == null) {
13.                  return null;
14.          }
15.          // 计算链表1中的节点个数
16.          int numOfListNode1 = 0;
17.          ListNode head1 = pHead1;
18.          while (head1 != null) {
19.              numOfListNode1++;
20.              head1 = head1.next;
21.          }
22.          
23.          // 计算链表2中节点个数
24.          int numOfListNode2 = 0;
25.          ListNode head2 = pHead2;
26.          while (head2 != null) {
27.              numOfListNode2++;
28.              head2 = head2.next;
29.          }
30.          
31.          // ⽐较两个链表的⻓度
32.          int step = numOfListNode1 - numOfListNode2;
33.          if (step > 0) {
34.              // 链表1更⻓，链表1移动
35.              while (step != 0) {
36.                  pHead1 = pHead1.next;
37.                  step--;
38.              }
39.          } else {
40.              // 链表2更⻓，链表2移动
41.              while (step != 0) {
42.                  pHead2 = pHead2.next;
43.                  step++;
44.              }
45.          }
46.          
47.          // 循环遍历后⾯的节点，相等则返回
48.          while (pHead1 != null && pHead2 != null) {
49.              if (pHead1 == pHead2) {
50.                      return pHead1;
51.              } else {
52.                  pHead1 = pHead1.next;
53.                  pHead2 = pHead2.next;
54.              }
55.          }
56.          return null;
57.      }
58. }

复制代码

• 时间复杂度​：O(m+n)，需要遍历链表三次（两次计算长度，一次查找）
  
• ​空间复杂度​：O(1)，只使用常数级别额外空间
  

但是上⾯的做法，如果公共节点在最后⼀个，假设⼀个链表⻓度为 n ，⼀个为 m ，那么计算个数就要全部遍历，需要 n+m 。两个链表都移动，到最后⼀个节点的时候才相等，也是 n+m ，也就是 O(2*(n+m)) 。
双指针遍历法（最优）

有没有更加好⽤的做法呢？肯定有，我们来看：
两个链表分别是：

如果我在第⼀个链表后⾯拼接上第⼆个链表，第⼆个链表后⾯拼接上第⼀个链表，就会变成下⾯的样⼦：

发现了⼀个规律，也就是拼接之后的链表，是等⻓度的，第⼀个和第⼆个链表都从第⼀个开始⽐较，只要相等，就说明是第⼀个公共节点。也就是上⾯被圈起来的 6 节点。
原理如下：

• 设链表1独有部分长度为a，链表2独有部分长度为b，公共部分长度为c
  
• 指针p1路径：a + c + b
  
• 指针p2路径：b + c + a
  
• 两个指针路径长度相同，会在公共节点相遇
  

特殊情况处理：​​当两个链表没有公共节点时，两个指针会同时变为null，退出循环

1. public class Solution {
2.      public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
3.          // 只要有⼀个为空，就不存在共同节点
4.          if (pHead1 == null || pHead2 == null) {
5.                  return null;
6.          }
7.          
8.          ListNode head1 = pHead1;
9.          ListNode head2 = pHead2;
10.          while (head1 !=head2) {
11.              // 如果下⼀个节点为空，则切换到另⼀个链表的头节点，否则下⼀个节点
12.              head1 = (head1 == null) ? pHead2 : head1.next;
13.              head2 = (head2 == null) ? pHead1 : head2.next;
14.          }
15.          return head1;
16.      }
17. }

复制代码

• 时间复杂度​：O(m+n)，每个指针遍历两个链表各一次
  
• ​空间复杂度​：O(1)，只使用两个指针
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！