[LeetCode] Intersection of Two Linked Lists (C++)

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

Intersection of Two Linked Lists - LeetCode

두 연결리스트가 주어졌을 때 만나는 지점을 찾는 문제입니다. Discuss에서 나온 풀이를 참고하여 해결했는데, 매우 신기한 풀이였습니다. 투포인터를 이용한 풀이였는데, headA와 headB를 각각 p1, p2로 가리키고 각각 null을 가리킬 때마다 headA와 headB를 재할당하여 반복적으로 탐색을 하다보면 결국 p1과 p2가 만나게 됩니다.

 

/**
 * 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 *p1 = headA;
        ListNode *p2 = headB;
        
        if(p1 == NULL || p2 == NULL) return NULL;
        
        while(p1 != NULL && p2 != NULL && p1 != p2) {
            p1 = p1->next;
            p2 = p2->next;
            
            if(p1 == p2) break;
            
            if(p1 == NULL) p1 = headA;
            if(p2 == NULL) p2 = headB;
        }
        
        return p1;
    }
};