[7. 연결리스트] 7.9 단순 연결리스트에서 오른쪽 원형 시프트 구현하기

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

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

---

https://msugi.tistory.com/47

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

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

---

Q 7.9 단순 연결리스트에서 오른쪽 원형 시프트 구현하기

5 3 2 2 3 -> nullptr 과 같이 주어졌을때
1번 시프트 => 3 5 3 2 2 ->nullptr
2번 시프트 => 2 3 5 3 2 ->nullptr 과 같이 이동하면된다.

---

해당문제의 소스코드와 결과는 https://msugi.tistory.com/47 의 내부 내용으로 작성 했으나 한번 더 소스코드를 작성해보면 다음과 같다. 문제는 단순 연결리스트지만 이중 연결리스트로 구현하였다.

//문제에서 시작과 끝은 nullptr을 갖도록 요구
template<class T>
inline void LinkedList<T>::CyclicallyRightShfitList(List<T>* L, int k) //문제 7.9
{
    if (!L || k==0) { return; }
 
    Node<T>* moveHead = L->HeadNode;
    Node<T>* moveTail = L->TailNode;
 
    moveTail->NextNode = moveHead;
    moveHead->PrevNode = moveTail;
    for (int i = 0; i < k; i++)
    {
        moveTail = moveTail->PrevNode;
    }
    moveHead = moveTail->NextNode;
    L->HeadNode = moveHead;
    L->TailNode = moveTail;
 
    moveHead->PrevNode = nullptr;
    moveTail->NextNode = nullptr;
}

L3는 기존에 사용하던 L3를 그대로 사용하였다. L3 = <5, 6, 7, 8, 9>

// mainstd::cout << "\n7-9) ";
L3.CyclicallyRightShfitList(L3.list, 3);L3.PrintAllNode(L3.list);// 7-9

결과