[LeetCode] 160. Intersection of Two Linked Lists, Easy

1. 문제

• 단일 연결 리스트 headA, headB가 주어질 때, 두 연결 리스트의 요소 중 동일한 주소를 가지는 첫 번째 노드를 반환하라.
• 만약, 없다면 null을 반환하라.

2. 해결

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
      if (!headA || !headB) return null;

    let pA = headA;
    let pB = headB;

    while (pA !== pB) {
        // 한쪽 리스트가 끝에 도달하면 반대쪽 리스트의 head로 이동
        pA = pA ? pA.next : headB;
        pB = pB ? pB.next : headA;
    }

    return pA; // 교차 노드 또는 null 반환
};

• 일단 2중 for문으로 해결하려 했는데, 길이가 다른 조건 때문에 쉽지 않았다.
• 결국 채찍피티의 힘을 빌렸는데, 원리는 이렇다고 한다.
  • 두 연결 리스트를 탐색하는 2개의 포인터를 둔다.
  • 두 포인터는 각각 리스트의 끝에 도달하면 상대 연결 리스트의 head로 이동시켜서 탐색을 다시 한다.
  • 만약, 동일한 노드가 교차한다면, 해당 노드가 같은 주소를 공유하는 노드.
  • 교차하지 않고 둘 다 null에 도달하면 교차하는 노드가 없는 것.
• 난 이래서 코딩 테스트 문제가 싫은데, 도대체 이 문제만 보고 어떻게 하면 건너편으로 포인터를 넘길 생각을 할까? 많이 풀어보면 되나?
• 그냥 외우면 되긴 한다. 근데 이해하고 싶다. 다른 블로그 글들을 보면 이 같은 풀이로 7분만에 풀었다는데 진짜인가 싶기도 하다. 내가 멍청한거겠지.
• 일단 내가 이해한 바로 저 원리는 아래와 같다.
  • 두 연결 리스트의 교차점 전까지의 길이가 다르다 -> 길이를 맞춰서 비교해야 한다.
  • 다른 방식으로 맞출 수도 있지만, O(m+n) 시간 복잡도로 비교하려면 투 포인터를 이용해야 한다.
  • 둘 중 길이가 짧은 연결 리스트의 탐색을 다 끝내면, 길이가 긴 연결 리스트의 포인터는 두 길이의 차이만큼 노드를 남겨두고 넘어가지 않은 상태이다.
  • 이 포인터가 다른 연결 리스트로 넘어가는 순간, 두 포인터는 동일한 위치의 노드를 비교하고 있다.
  • 여기서부터 출발해서 동일한 주소를 가지는 노드를 반환한다. 만약 없으면 null 반환.
• 이렇게 하면, 길이가 짧은 연결 리스트의 시작 노드를 기준으로 두 연결 리스트의 노드들을 비교할 수 있다.