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

题目描述

输入两个链表，找出它们的第一个公共节点。

解题思路

我们先计算两个链表的长度，然后把两个头节点移动到同一个起跑线上。在这个基础上，同时移动两个链表指针，直到二者相等，或都到达尾节点（返回NULL）。

代码

class Solution {
 public:
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (!headA || !headB) return nullptr;
    ListNode *ptra = headA, *ptrb = headB;
    int lena = 0, lenb = 0;
    while (ptra) {
      ++lena;
      ptra = ptra->next;
    }
    while (ptrb) {
      ++lenb;
      ptrb = ptrb->next;
    }
    ptra = headA;
    ptrb = headB;
    if (lena > lenb) {
      int distance = lena - lenb;
      while (distance) {
        ptra = ptra->next;
        --distance;
      }
    } else if (lena < lenb) {
      int distance = lenb - lena;
      while (distance) {
        ptrb = ptrb->next;
        --distance;
      }
    }
    while (ptra) {
      if (ptra == ptrb) return ptra;
      ptra = ptra->next;
      ptrb = ptrb->next;
    }
    return nullptr;
  }
};

结果

执行结果：通过

执行用时：52 ms, 在所有 C++ 提交中击败了77.68%的用户

内存消耗：14.7 MB, 在所有 C++ 提交中击败了32.08%的用户