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

/*
@ 수정 25. 02. 21

• 불필요하게 동적할당 되어있던 List1, List2 를 삭제
• main에서 L4의 순환구조 뒤에 L3를 더하는 구조가 아닌 L4순환구조에서 L3의 마지막 노드가 참조하는 방식으로 변경  (L3.list->TailNode->NextNode = L4.list->HeadNode)

*/

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

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

---

https://msugi.tistory.com/47

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

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

---

Q 7.4 사이클이 없는 두 리스트가 겹치는지 확인하기

L1->1->2↘
L2->3->4->5->6->nullptr
과 같이 겹치는 연결리스트가 있을때 겹치는 구간을 출력하라.

---

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

// 7.4 사이클이 없는 두 리스트가 겹치는지 확인하기#include "LinkedList.h"
 
int Length(Node<int>* L)
{
    int length = 0;
    while (L)
    {
        length++;
        L = L->NextNode;
    }
    return length;
}
void AdvanceListByK(int k, Node<int>** L)
{
    while (k--)
    {
        *L = (*L)->NextNode;
    }
}
 
Node<int>* OverLappingNoCycleLists(List<int>& L1, List<int>& L2)
{
    Node<int>* NodeL1 = L1.HeadNode;
    Node<int>* NodeL2 = L2.HeadNode;
 
    int L1_Len = Length(NodeL1);
    int L2_Len = Length(NodeL2);
 
    AdvanceListByK(abs(L1_Len - L2_Len), L1_Len > L2_Len ? &NodeL1 : &NodeL2);
 
    while (NodeL1 && NodeL2 && NodeL1 != NodeL2)
    {
        NodeL1 = NodeL1->NextNode;
        NodeL2 = NodeL2->NextNode;
    }
    return NodeL1;
}

 

// mainLinkedList<int> L3, L4;
int T3;
 
L4.AddNode(L4.list, L4.CreateNode(0));
for (int i = 1; i < 5; i++)
{
    L4.AddNode(L4.list, L4.CreateNode(i));
    L3.DelNode(L3.list, i);
}
L4.list->TailNode->NextNode = nullptr;
L4.list->HeadNode->PrevNode = nullptr;
L3.list->TailNode->NextNode = L4.list->HeadNode->NextNode;
T3 = NULL;
T3 = OverLappingNoCycleLists(*L3.list, *L4.list)->data;
if (!T3)
{
    std::cout << "\n7-4) " << "두 리스트가 겹치는 지점이 존재하지 않습니다." << std::endl; //7-4
}
else
{
    std::cout << "\n7-4) " << "두 리스트가 겹치는 지점 :" << T3 << std::endl; //7-4
}

 

문제 7.3 에서 사용한 L3 다시 사용했으며 해당 문제의 예시를 만들기 위해 List의 내용을 main과 같이 수정하였다.

결과