[7. 연결리스트] 7.5 사이클이 존재하는 두 리스트가 겹치는지 확인하기

/*
@ 수정 25. 02. 21

• main에서 L5의 리스트 구조를 L4와 동일하지만 순환되도록 (L3.list가 L5를 참조) 수

*/

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

---

https://msugi.tistory.com/47

[7. 연결리스트] 7.0 연결리스트 기초 작업

연결리스트 문제를 풀기전 LinkedList를 위와 같이 직접 구현했다. 위 LikedList를 이용하여 문제를 풀 예정이다.

---

Q 7.5 사이클이 존재하는 두 리스트가 겹치는지 확인하기
L1->1->2↘
L2->3->4->5->6->(L2->NextNode(3))
과 같이 겹치는 연결리스트가 있을때 겹치는 구간을 출력하라.

---

해당 내용의 소스코드와 결과는 다음과 같다.

// 7.5 사이클이 존재하는 두 리스트가 겹치는지 확인하기#include "LinkedList.h"
#include "7.3 사이클이 존재하는지 확인하기.h"
#include "7.4 사이클이 없는 두 리스트가 겹치는지 확인하기.h"
 
Node<int>* OverlappingLists(List<int>* L1, List<int>* L2)
{
    auto root1 = HasCycle(*L1);
    auto root2 = HasCycle(*L2);
 
    if (!root1 && !root2)
    {
        return OverLappingNoCycleLists(*L1, *L2);
    }
    else if ((root1 && !root2) || (!root1 && root2))
    {
        return nullptr;
    }
 
    auto temp = root2;
    do
    {
        temp = temp->NextNode;
    } while (temp != root1 && temp != root2);
 
    return temp == root1 ? root2 : nullptr;
 
}

문제 7.4에서 구현한 Node<int>* OverLappingNoCycleLists(List<int>& L1, List<int>& L2) 함수를 그대로 사용했다.

// mainLinkedList<int> L3, L5;
int T3;
 
for (int i = 1; i < 10; i++)
{
    L5.AddNode(L5.list, L5.CreateNode(i));
}
 
T3 = NULL;
T3 = OverlappingLists(L3.list, L5.list)->data;
if (!T3)
{
    std::cout << "\n7-5) " << "두 리스트가 겹치는 지점이 존재하지 않습니다." <<std::endl; //7-5
}
else
{
    std::cout << "\n7-5) " << "두 리스트가 겹치는 지점 :" << T3 << std::endl; // 7-5
}

 

문제 7.1 main의 내용중 L5가 for문에 포함된 내용을 그대로 사용했으며 문제 7.4의 L3, L4 를 그대로 사용하였다.

결과