# 160. Intersection of Two Linked Lists
Difficulty: Easy

## Solution

/**
*** Author: R-CO
*** E-mail: [e-mail]
*** Date: 2020-10-07
**/
#include <cstdlib>
#include <iostream>
using std::cout;
using std::endl;

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

#define SOLUTION_VERSION 1

#if (SOLUTION_VERSION == 1)

#include <unordered_set>
using std::unordered_set;

class Solution
{
 public:
 	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
		unordered_set<ListNode*> node_set;
		ListNode *intersection_node = nullptr;

		for (auto *p = headA; p != nullptr; p = p->next) {
			node_set.insert(p);
		}

		for (auto *p = headB; p != nullptr; p = p->next) {
			if (node_set.find(p) != node_set.end()) {
				intersection_node = p;
				break;
			}
		}

		return intersection_node;
	}
};

#elif (SOLUTION_VERSION == 2)

class Solution
{
 public:
 	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
		if (headA == nullptr || headB == nullptr) {
			return nullptr;
		}

		ListNode *intersection_node = nullptr;
		ListNode *p1 = headA;
		ListNode *p2 = headB;
		ListNode *tailA = nullptr;
		ListNode *tailB = nullptr;
		bool has_a_reach_end = false;
		bool has_b_reach_end = false;
		ListNode *headArray[2] = {headA, headB};
		int p1_point_to = 0; // 0 => A, 1 => B
		int p2_point_to = 1; // 0 => A, 1 => B

		while (true) {
			if (p1 == p2) {
				intersection_node = p1;
				break;
			}

			if (has_a_reach_end && has_b_reach_end && tailA != tailB) {
				break;
			}

			if (p1->next == nullptr) {
				if (!has_a_reach_end) {
					has_a_reach_end = true;
					tailA = p1;
				}
				p1_point_to = (p1_point_to + 1) % 2;
				p1 = headArray[p1_point_to];
			} else {
				p1 = p1->next;
			}
			
			if (p2->next == nullptr) {
				if (!has_b_reach_end) {
					has_b_reach_end = true;
					tailB = p2;
				}
				p2_point_to = (p2_point_to + 1) % 2;
				p2 = headArray[p2_point_to];
			} else {
				p2 = p2->next;
			}
		}

		return intersection_node;
	}
};

#else
	#error "Please check define \"SOLUTION_VERSION\""
#endif

int main(int argc, char *argv[])
{
	return EXIT_SUCCESS;
}

## Result

Success
Details
Runtime: 40 ms, faster than 96.95% of C++ online submissions for Intersection of Two Linked Lists.
Memory Usage: 14.6 MB, less than 77.62% of C++ online submissions for Intersection of Two Linked Lists.

###### tags: `LeetCode-Easy` `C++`