160. Intersection of Two Linked Lists

https://leetcode.com/problems/intersection-of-two-linked-lists/

Intersection of Two Linked Lists - LeetCode

 

 

두 연결리스트의 합쳐지는 부분(intersection)을 구하는 문제이다.

 

 

---

 

1. 문제 이해

 

=> 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. (두 단일 연결리스트 headA와 headB가 주어지면, 그 연결리스트의 합쳐지는 지점을 리턴하라. 만일 없으면, NULL을 리턴하라.)

 

=> It is guaranteed 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. (연결리스트를 변형하지 마라.)

 

제한사항

• The number of nodes of listA is in the m.
• The number of nodes of listB is in the n.
• 0 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• intersectVal is 0 if listA and listB do not intersect.
• intersectVal == listA[skipA + 1] == listB[skipB + 1] if listA and listB intersect.

....뭐 그렇다네. 막상 이렇게 보니까 와닿지는 않는다.

 

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

Output: Intersected at '8'

 

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

Output: Intersected at '2'

 

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

Output: No intersection

 

인풋과 아웃풋은 이렇고... 

 

Follow up: Could you write a solution that runs in O(n) time and use only O(1) memory?

(님 O(1) 메모리와 O(n) 시간안에 해결한가요?)

 

암튼 이 문제는, 두 연결 리스트의 각각의 헤드 노드가 주어지고, 이 두 헤드노드로 연결 리스트의 합쳐지는 부분을 리턴하는 거다. 만일 없으면 NULL을 반환하고. 

 

 

 

---

 

2. 문제 재정의

 

headA, headB를 이용하여 연결 리스트를 순회하면서 처음으로 공통되는 노드가 있을 시 그 노드를 리턴하는 문제인 것 같음. 무조건 headA, headB를 쓸 필요는 없지만. 재정의라고 하기에는 문제가 원하는 요구가 명확하네...ㅋㅋㅋㅋ

 

 

 

 

---

 

3. 계획 수립

 

 

1) set으로 A연결리스트를 순회하며 노드들을 담은 다음, B연결리스트를 순회하며 만일 중복되는 지점이 있을 시 그 지점을 리턴하는 방식을 생각해 볼 수 있다. 하지만 이는 O(n)메모리이므로 넘기도록 한다!!(ㅠㅠ) 이 방법으로 했을 시, 시간 복잡도 O(n)이며 제한사항, intersection 유무의 모든 경우에 오류 없이 잘 동작하지 싶다. 만일 공통되는 부분이 없을 시엔, 그냥 B연결리스트 쭉 순회 후 NULL을 반환하면 되니까.

 

 

2) 투포인터 방식을 생각해 볼 수 있다. 일단 두 연결 리스트의 길이를 동일하게 맞춰준 다음, ptr을 한칸씩 움직이며 노드가 같은지 확인하면 된다. 두 연결리스트의 길이를 동일하게 맞춰주는 것은 연결리스트를 자르는 것이 아니라, 두 연결 리스트의 길이 차이를 고려해 ptr 순회 지점을 설정해준다는 것이다. 이 방식은 O(1)의 메모리를  만족한다.

 

 

---

 

4. 계획 검증 

 

 

투포인터 방식 사용시, intersection 유무에 상관없이 오류없이 동작한다. ptr 순회가 끝나면 NULL을 반환하면 되고, 그 전에 공통되는 부분을 찾을 시 바로 노드를 return하니까. O(1)의 메모리에도 들어가고, O(n)의 시간 복잡도 또한 만족한다. 빈 노드가 입력되었을 시에도 동작한다.

 

---

 

 

5. 프로그램 구현 

 

/**
 * 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) {
        ListNode *ptrA = headA, *ptrB = headB;
        int sizeA = 0, sizeB = 0, size = 0;
        
        while (ptrA != nullptr) {
            ptrA = ptrA->next;
            sizeA++;
        };
        while (ptrB != nullptr) {
            ptrB = ptrB->next;
            sizeB++;
        };
        
        size = sizeA > sizeB ? sizeB : sizeA;
        
        ptrA = headA;
        ptrB = headB;
        
        for (int i = 0; sizeA - size > i;i++) ptrA = ptrA->next;
        for (int i = 0; sizeB - size > i;i++) ptrB = ptrB->next;
        
        while (ptrA != nullptr && ptrB != nullptr) {
            if (ptrA == ptrB)
                return ptrA;
            ptrA = ptrA->next;
            ptrB = ptrB->next;
        };
        
        return nullptr;
    }
};

 

---

 

6. 피드백 & 복기

 

/**
 * 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) {
    ListNode *a = headA;
    ListNode *b = headB;

    while(a != b) {
        a = a == nullptr ? headB: a->next;
        b = b == nullptr ? headA: b->next;
    }
    
    return a;
        
    }
};

 

??? 어케했노

 

 

아 A 연결리스트에서 B 연결리스트로 넘어가서 순회하면, 끝까지 이동하는 총 길이는 A + B가 되고 B에서 A로 넘어갈때도 동일하겠네.

즉 A + B = B + A라서 연결점이 없을때도 마지막에 둘 다 nullptr에 동일하게 도달하고, 그렇지 않다면 중간에 만나겠네.(이런 생각하는 사람들 가끔 보면 경외감 든다)