[leetcode] Intersection of Two Linked Lists

Description

Intersection of Two Linked Lists

두 개의 Linked List가 주어졌을 때, 이 Linked List의 교차점을 찾는 문제이다. 교차점이 없다면 null을 반환한다.

Solution

두 개의 포인터가 각 Linked List의 노드를 순회한다. 이때, 두 개의 Linked List의 길이가 다를 수 있다는 점이 핵심 포인트이며, 두 리스트의 길이 차이를 상쇄시키는 것이 중요하다.

두 Linked List의 길이는 두 리스트를 합치면 된다. List A의 끝에 도달했을 때는 List B의 시작으로 이동하고, List B의 끝에 도달했을 때는 List A의 시작으로 이동한다.

List A는 [1,2,3,4,5], List B는 [6,7,4,5]일 때 교차점은 4이다. 리스트가 끝나는 지점에서 다른 리스트를 이어붙이면 교차점 이전의 부분은 상쇄가 된다.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    if(!headA || !headB) return null;
    
    let curA = headA;
    let curB = headB;
    
    while(curA !== curB){
        if(curA === null) curA = headB;
        else curA = curA.next;
        
        if(curB === null) curB = headA;
        else curB = curB.next;
    }

    return curA;
};

두 포인터가 각각 List A와 List B를 순회하기 때문에, 시간 복잡도 O(M+N)는 두 포인터가 이동한 총 거리(M+N)가 된다. 공간 복잡도의 경우, 두 개의 포인터를 사용하지만 포인터의 개수는 일정하고, 추가적인 메모리 구조를 생성하지 않기 때문에 O(1)이 된다.