链表算法

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。

请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。

解题思路

暴力法(硬做）。链表1到末尾，链表2也到末尾，判断是不是节点地址是不是同一个。如果是同一个，两个链表一起往后退，直到找到不相等的节点，下一个节点就是X。

时间复杂度是O(m + n).

空间复杂度是O(1).



用集合判重。第一个链表m所有元素都加到set里，第二个链表每个节点比较，如果有在set里，说明有重叠。重叠的第一个节点，就是重合的x节点。

时间复杂度O(1)

空间复杂度O(m)

ListNode* get_first_match_node(ListNode* head1, ListNode* head2) {
  if (head1 == nullptr || head2 == nullptr) return nullptr;
  unordered_set<ListNode*> s;
  while (head1) {
    s.insert(head1);
    head1 = head1->next;
  }
  while (head2) {
    if (s.find(head2) != s.end()) return head2;
    head2 = head2->next;
  }
  return nullptr;
}