1 截断成等长的链表

1. 先获取两个链表的长度；

2. 让长的链表先走长度的差值，这样剩下的两条链表长度一样；

3. 依次比较链表的节点地址；

4. 地址相同则找到，到链表尾部还没找到则返回空；

// Definition for singly-linked list.
struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
      if (!headA || !headB) return nullptr;
      int len1 = 0, len2 = 0;
      ListNode* h1 = headA, *h2 = headB;

      while(h1) {
        ++len1;
        h1 = h1->next;
      }

      while(h2) {
        ++len2;
        h2 = h2->next;
      }

      int x = 0;
      if (len1 < len2) {
        h1 = headB;
        h2 = headA;
        x = len2 - len1;
      } else {
        h1 = headA;
        h2 = headB;
        x = len1 - len2;
      }

      for (int i = 0; i < x; ++i) {
        h1 = h1->next;
      }

      while (h1) {
        if (h1 == h2) return h1;
        h1 = h1->next;
        h2 = h2->next;
      }

      return nullptr;
    }
};

2 连接成等长的链表 优雅！！

1. 相交部分的长度为 c，headA的不相交部分长度为 a， headB的不相交部分为 b；

2. 双指针同时从headA和headB开始走，比较节点地址；

3. 如果headA走到头，则回到headB的起始位置，如果headB走到头，则回到headA的起始位置；

4. 最终走的长度为：

   • 如果a等于b：两个链表走的长度都是a；

   • 如果a不等于b：两个链表走的长度是 a+c+b 和 b+c+a，长度一样，即到达了相交点。

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