LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 用哈希表存储第一个链表的节点，遍历第二个链表，如果在哈希表中存在当前节点，则该节点为相交节点

class Solution {
 public:
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    unordered_set<ListNode *> s;
    ListNode *cur = headA;
    while (cur) {
      s.emplace(cur);
      cur = cur->next;
    }
    cur = headB;
    while (cur) {
      if (s.count(cur)) {
        return cur;
      }
      cur = cur->next;
    }
    return nullptr;
  }
};

• 用两个指针 a 和 b 从两个链表头开始遍历，a 到达尾部之后则从 headB 开始继续遍历，b 到达尾部之后则从 headA 开始继续遍历，最终两者相遇处即为相交节点

1-2-3-4-5-6-7
     /
  8-9

1234567894
8945671234

原理如下，两条链表相交，则尾部必然有相同的子链表，因此可看作
$$$x // A 链表，x 为 A、B 链表相同部分
@@@x // B 链表
$$$的长度 + x的长度 + @@@的长度 = @@@的长度 + x的长度 + $$$的长度
a 走过 $$$x@@@ 时，到达 B 链表的 x
b 走过 @@@x$$$ 时，到达 A 链表的 x
因此 ab 相遇处即为链表相交处

• 实现如下

class Solution {
 public:
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *a = headA;
    ListNode *b = headB;
    while (a != b) {  // 若不相遇，遍历完两个链表时，两个指针都为空，退出循环
      a = a ? a->next : headB;
      b = b ? b->next : headA;
    }
    return a;
  }
};