[알고리즘] Leetcode. Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

• intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
• listA - The first linked list.
• listB - The second linked list.
• skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
• skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

 

cycle이 없는 두 개의 linked list가 있고 두 리스트가 교차점이 있다면 그 교차점을 반환하고 없다면 null을 반환하는 문제

---

이런식으로 모두 다 순회해야 하는 알고리즘을 Brute Force 알고리즘이라고 부르는 것 같다. 무식한 힘이라는 뜻..? 

장점으로는 오차 없이 계산할 수 있는 게 장점이라고 한다.

---

처음 생각한 방법

1. headA, headB 길이를 구하고 길이가 더 긴 리스트의 앞부분을 자르고 길이를 똑같이 만든 후 비교하기

 

var getLength = function(head) {
    let length = 0;
    while (head.next) {
        head = head.next;
        length++;
    }
    return length;
}

var getIntersectionNode = function(headA, headB) {
    const lengthA = getLength(headA);
    const lengthB = getLength(headB);
    let long;
    let short;

    for (let i = 0; i < Math.abs(lengthA - lengthB); i++) {
        if (lengthA > lengthB) {
            headA = headA.next;
        } else {
            headB = headB.next;
        }
    }
    
    while (headA !== headB) {
        if (!headA.next) return null;
        
        headA = headA.next;
        headB = headB.next;
    }
    return headA;
}

 2. 각 리스트를 순회하고 null에 다다랐을 때 다른 리스트로 이어서 순회하여 각각 비교하기

순회한다면 각각의 끝부분에서 다른 리스트로 바꾸었을 때 

A : 4 -> 1 -> 8 -> 4 -> 5 (마지막) B로 바꿈 -> 5 -> 6 -> 1 -> 8 -> 4 -> 5

B : 5 -> 6 -> 1 -> 8 -> 4 -> 5 (마지막) A로 바꿈 -> 4 -> 1 -> 8 -> 4 -> 5

 

결국에 마지막 부분은 같게 된다. 이걸 이용하여 풀면 구할 수 있다. (와 난 왜 이런 방법을 못생각했을까!) 

var getIntersectionNode = function(headA, headB) {
    if (!headA || !headB) return null;

    let a = headA;
    let b = headB;
    let numA = 0;
    let numB = 0;
    
    while (a !== b) {
        if (a.next === null) {
            if (numA > 1) return null;
            numA++;
            a = headB;
        } else {
            a = a.next;
        }
        if (b.next === null) {
            if (numB > 1) return null;
            numB++;
            b = headA;
        } else {
            b = b.next;
        }
    }
    
    return a;
};