[해커랭크] Find Merge Point of Two Lists (C++)

문제 링크: www.hackerrank.com/challenges/find-the-merge-point-of-two-joined-linked-lists/problem?h_r=internal-search

Find Merge Point of Two Lists | HackerRank

1. 주의할 점

- 최악의 경우 N*M의 시간복잡도가 발생하지만, 통과한다

 

2. 구현

- While문 2개를 이용해서 브루트포스 느낌으로 구현할 수 있지만, Discussion에서 다른 사람의 풀이를 통해 살짝(?) 다른 접근을 해보자

- head1와 같은 주소를 가리키는 a를, head2와 같은 주소를 가리키는 b를 생성한다

- 주소 a와 b가 같을때까지 While문을 수행하며 둘 모두 한칸씩 이동한다(다음 칸으로). 단, 각자 확인하던 List가 끝난 경우에는 다른 List의 Head를 참조하도록 설정한다(A->B->A->B->A->...)의 순서와 같이 설정

- 둘이 같은 주소를 공유한 지점에선 a->data나 b->data를 출력하면 된다

int findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    SinglyLinkedListNode* a = head1;
    SinglyLinkedListNode* b = head2;
    while(a!=b){
        if(a->next == nullptr)
            a = head2;
        else
            a = a->next;
        
        if(b->next == nullptr)
            b = head1;
        else
            b = b->next;
    }
    return a->data;
}