160. 相交链表

二刷

class solution {
  int listlength(listnode *head) {
    int length = 0;
    while (head) {
      ++length;
      head = head->next;
    }
    return length;
  }
public:
  listnode *getintersectionnode(listnode *heada, listnode *headb) {
    int lengtha = listlength(heada);
    int lengthb = listlength(headb);
    int diff = std::abs(lengtha - lengthb);
    if (lengtha > lengthb)
      while (diff--)
        heada = heada->next;
    else
      while (diff--)
        headb = headb->next;
    while (heada != headb) {
      heada = heada->next;
      headb = headb->next;
    }
    return heada;
  }
};

要我说我这个怎么就不是 \(\mathrm O(n+m)\) 了？不就是常数大了一倍吗？嗯？但是说实话官解真有点厉害的，这个思路太精妙了，其实就是利用了两个相同的数相加必定是偶数的原理，管你是奇是偶，先走两遍再说。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }
};

但是这个 unordered_set 解法也还是得考虑考虑：其实在这道题里，先后遍历（而不是硬要求所谓的双指针一次遍历）是更好的选择。它比较直观，而且省去了一些 contains() 的调用，理论上来说常数要更小一些。

class Solution {
public:
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    unordered_set<ListNode *> Visited;
    while (headA) {
      Visited.insert(headA);
      headA = headA->next;
    }
    while (headB) {
      if (Visited.contains(headB))
        return headB;
      headB = headB->next;
    }
    return {};
  }
};

三刷

class Solution {
public:
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *CurA = headA, *CurB = headB;
    while (CurA || CurB) {
      if (!CurA)
        CurA = headB;
      if (!CurB)
        CurB = headA;
      if (CurA == CurB)
        return CurA;
      CurA = CurA->next;
      CurB = CurB->next;
    }
    return nullptr;
  }
};

上面写的都是什么破玩意，我这写得多好。