# LeetCode Easy 160. Intersection of Two Linked Lists

tags: leetcode

問題

• Explore
• Problems

アイデア

｢2つの単一方向リストの共通部分がどこノードから始まるのかを探せ｣という問題です．

普通に1つ1つノードを辿っていけば良いでしょう．

解法

• 2つのリストをそれぞれA，Bとします．
• この際，それぞれのリストの参照するノードをcurA, curBとします．
• まず，curAが終端に至ったら，Bの先頭に繋げます．同様にcurBが終端に至ったら，Aの先頭に繋げます．
• そして，curA == curBになった際のノードが答えです．

Floyd's cycleを利用した解答です．

計算量

リストのノードの数をそれぞれN，Mとします．

• 時間計算量
  • $O(N + M)$
• 空間計算量
  • $O(1)$

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    auto curA = headA, curB = headB;
    auto isCycledA = false, isCycledB = false;
    
    while (curA && curB) {
      if (curA == curB)
        return curA;
      
      curA = curA->next;
      if (!isCycledA && !curA) {
        curA = headB;
        isCycledA = true;
      }
      
      curB = curB->next;
      if (!isCycledB && !curB) {
        curB = headA;
        isCycledB = true;
      }
    }
    return NULL;
  }
};