[7. 연결리스트] 7.2 부분 리스트 하나 뒤집기

/*
@ 최종 수정 25. 02. 20

• 7.1 두 개의 정렬된 리스트 합치기 에서 사용된 L1, L2 를 다시 사용하는 과정에서 같은 데이터 값인데 다른 메모리 주소를 가리키는 문제로 뒤집어진 리스트의 PrevNode의 주소가 다른 주소를 가리키는 현상 수정
• 함수의 타입을 List<int>* 타입에서 void 타입으로 변경
• DummyList를 리턴하는 방식에서 변경된 주소가 바로 List<int> L에 반영되도록 수정(따라서 return이 필요없어짐)
• DummyList의 리턴삭제로 delete DummuList 추가
• 불필요한 int k 삭제 int count를 한번더 사용하는 방식으로 변경
• main에서 다른 문제에서 사용하는 불필요한 변수 삭제(7-1의 변수는 해당 변수를 그대로 사용해서 유지)

*/

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

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

---

https://msugi.tistory.com/47

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

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

---

Q 7.2 부분 리스트 하나 뒤집기

리스트의 부분 리스트를 역순으로 재배열 하는 문제를 풀어보자.

EX)
L->11->7->6->5->3->2->nullptr 2번째와 5번째 노드를 포함하여 뒤집어라 의 결과는 다음과 같다.
L->11->3->5->6->7->2->nullptr 

---

해당 문제의 소스코드와 결과는 다음과 같다.

// 7.2 부분 리스트 하나 뒤집기#include "LinkedList.h"
 
void ReverseSublist(List<int>& L, int start, int finish)
{
    List<int>* DummyList = new List<int>();
    Node<int>* DummyHead = new Node<int>();
    DummyHead->NextNode = L.HeadNode;
    auto subListStart = DummyHead;
    int count = 1;
    
    while (count++ < start)
    {
        subListStart = subListStart->NextNode;
    }
 
    auto subList_iter = subListStart->NextNode;
    auto Previter = subList_iter;
    count = 0;
    while (start++ < finish)
    {
        auto tempNext = subList_iter->NextNode;
        subList_iter->NextNode = tempNext->NextNode;
        tempNext->NextNode = subListStart->NextNode;
        subListStart->NextNode = tempNext;
 
        
        tempNext->PrevNode = subListStart;
        Previter->PrevNode = tempNext;
        Previter = Previter->PrevNode;
        subList_iter->NextNode->PrevNode = subList_iter;
        count++;
    }
    subList_iter->NextNode->PrevNode = subList_iter;
 
    DummyList->HeadNode = DummyHead->NextNode;
 
    delete DummyHead;
    delete DummyList;
 
}

i번째와 j번째 노드를 선택한다고 할때 j까지만 순회하면되서 O(j)의 시간 복잡도를 가지게 된다.

// 7.2 mainLinkedList<int> L1,L2,L3;
 
for (int i = 1; i < 10; i++)
{
    if (i % 2 == 0)
    {
        L1.AddNode(L1.list, L1.CreateNode(i));
    }
    else
    {
        L2.AddNode(L2.list, L2.CreateNode(i));
    }
   
}
std::cout << "\n7-1) ";
L1.PrintAllNode(L1.list);
L2.PrintAllNode(L2.list);
 
 
L3.list = MergeTwoSortedLists(*L1.list, *L2.list); //7-1
L3.PrintAllNode(L3.list);
 
std::cout << "\n7-2) ";
ReverseSublist(*L3.list, 2, 5); //7-2
L3.PrintAllNode(L3.list);

L3는 문제 7.1 에서 사용한 L3를 그대로 사용했다. 

결과