Leet Code - 160. Intersection of Two Linked Lists(C++)

예제: Intersection of Two Linked Lists

문제
Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

풀이

이 문제는 두 linked list가 만나는 노드가 있다면 해당 주소값을 return하는 문제이다.

필자는 아쉽게도 아직까지는 머리가 번뜩이지 않기 때문에 이 문제를 봤을 때 unordered_map이 바로 떠올랐다.
headA의 주소값을 unordered_map에 저장하고, headB를 순회하면서 값을 unordered_map에 값이 있다면 해당 주소값을 바로 return해주는 로직을 구현한 것이 아래 CASE1번 코드다.

그런데 속도가 좀 아쉽다.
그래서 부끄럽게도 다른 사람들의 풀이를 조금 답습 하다가, 기발한 풀이를 발견했다.
간단히 말하자면, 두 linked list의 길이를 맞추기만 하면 1:1 매칭으로도 답을 알 수 있다는 것이다.
즉, headA = [1, 2, 3, 4, 5], headB = [1, 4, 5]라면, headA에서는 '3'에 해당하는 index에서부터 비교하면 되는 것이다.
이를 구현한것이 CASE2번 코드이다.

전체적인 소스코드는 아래와 같다.

소스 코드

/* CASE1 */
/**
 * 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) {
		unordered_map<ListNode*, int> um;
		while (headA != NULL) {
			um[headA]++;
			headA = headA->next;
		}

		while (headB != NULL) {
			if (um[headB]) {
				return headB;
			}
			headB = headB->next;
		}

		return NULL;
	}
};

/* CASE2 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	int length(ListNode *node) {
		int len = 0;
		while (node) {
			len++;
			node = node->next;
		}
		return len;
	}

	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
		ListNode* ha = headA;
		ListNode* hb = headB;

		int len = length(headA) - length(headB);

		while (len > 0) {
			len--;
			ha = ha->next;
		}
		while (len < 0) {
			len++;
			hb = hb->next;
		}

		while (ha && hb) {
			if (ha == hb) {
				return ha;
			}
			ha = ha->next;
			hb = hb->next;
		}

		return NULL;
	}
};

풀이 후기

Leet Code는 좋은 것이 서로 코드를 공유하고 의견을 나눌 수 있다는 것 같다.
물론 뻔한 코드도 많지만 정말 기발한 코드도 넘쳐난다.
나도 알고리즘을 계속 풀다보면 그 기발함을 조금 깨우칠 수 있지 않을까.