两个链表的第一个公共节点

---

题目：

题解：

1、哈希表法

• 解题思想：先把链表headA都放在set集合中，然后循环链表 headB比较 headB和headA的==指针==是否有相同，相同则，说明找到了第一个公共节点，返回该指针。否则没无公共节点，返回null。

• 复杂度分析

  • **时间复杂度：O(m+n)**，其中 m 和 n 是分别是链表 headA 和 headB 的长度。需要遍历两个链表各一次。

  • **空间复杂度：O(m)**，其中 m 是链表 headA 的长度。需要使用哈希集合存储链表 headA 中的全部节点。

• 代码：

  // 哈希表法
  class Solution2 {
      public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
          Set<ListNode> visited = new HashSet<ListNode>();
          ListNode temp = headA;
          while (temp != null) {
              visited.add(temp);
              temp = temp.next;
          }
          temp = headB;
          while (temp != null) {
              // 如果set集合包含temp指针，则headA和headB链表有相同的指针
              if (visited.contains(temp)) {
                  return temp;
              }
              temp = temp.next;
          }
          return null;
      }
  }

2、双指针

• 解题思路：

• 复杂度分析：

  • **时间复杂度：O(m+n)**，其中 m 和 n 是分别是链表 headA 和 headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。

  • **空间复杂度：O(1)**。

• 代码：

  // 双指针
  public class Solution {
      public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
          ListNode a = headA;
          ListNode b = headB;
          while(a != b) {
              a = a != null ? a.next : headB;
              b = b != null ? b.next : headA;
          }
          return a;
      }
  }