LeetCodeDay43 —— 相交链表★☆

160. 相交链表

描述

• 编写一个程序，找到两个单链表相交的起始节点。

示例

例如，下面的两个链表：
A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗
B:     b1 → b2 → b3
在节点 c1 开始相交。

注意：
  如果两个链表没有交点，返回 null.
  在返回结果后，两个链表仍须保持原有的结构。
  可假定整个链表结构中没有循环。
  程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

思路

1. 计算出两链表的长度差，然后让长的链表先走diff步，两个链表一起走，若能相遇则为相交的起始点。
2. 实现上可以利用两个指针同时后移，当一个指针移到末尾时，另一个指针到末尾的距离即为两者的差值。

class Solution_160_01 {
 public:
  ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    if (!headA || !headB) return NULL;
    int lenA = 0, lenB = 0;
    ListNode *longNode = headA, *shortNode = headB;
    while (longNode) {
      ++lenA;
      longNode = longNode->next;
    }
    while (shortNode) {
      ++lenB;
      shortNode = shortNode->next;
    }
    int diff = lenA - lenB;
    longNode = headA;
    shortNode = headB;
    if (lenA < lenB) {
      diff = -diff;
      longNode = headB;
      shortNode = headA;
    }
    for (int i = 0; i < diff; ++i) {
      longNode = longNode->next;
    }
    while (longNode && shortNode && longNode != shortNode) {
      longNode = longNode->next;
      shortNode = shortNode->next;
    }
    return longNode;
  }
};

// 另一种更清晰的实现方式，不必具体计算出diff，利用双指针计算出两链表差值
class Solution_160_02 {
 public:
  ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    ListNode *p = headA, *q = headB;
    while (p && q) {
      p = p->next;
      q = q->next;
    }
    while (p) {
      p = p->next;
      headA = headA->next;
    }
    while (q) {
      q = q->next;
      headB = headB->next;
    }
    while (headA && headB && headA != headB) {
      headA = headA->next;
      headB = headB->next;
    }
    return headA;
  }
};