[C++] 리스트 inverting 체인연산

#include <iostream>

typedef struct listNode *listPtr;
typedef struct listNode
{
    char data;
    listPtr link;
}listNode;

listPtr invert(listPtr lead)
{
    listPtr middle, tail;
    middle = NULL;

    // 여기서 쓰이는 lead, middle, tail 은 임시로 거쳐가는 변수임.
    while(lead)
    {
        tail = middle;          // tail 은 middle 을 취함.
        middle = lead;          // middle 은 lead 를 취함.
        lead = lead->link;      // lead는 lead 의 link 를 취함.
        
        middle->link = tail;    // tail 부분은 middle 부분보다 앞부분의 Link 일것임. 때문에 이 부분을 할당함.
    }

    return middle;
}

int main()
{
    listPtr l1, l2, l3, l4, l5;

    l1 = new listNode();
    l2 = new listNode();
    l3 = new listNode();
    l4 = new listNode();
    l5 = new listNode();
    
    l1->data = 'a';
    l2->data = 'b';
    l3->data = 'c';
    l4->data = 'd';
    l5->data = 'e';

    l1->link = l2;
    l2->link = l3;
    l3->link = l4;
    l4->link = l5;
    l5->link = NULL;

    auto link = l1;

    while(link != NULL)
    {
        std::cout << link->data << std::endl;
        link = link->link;
    }
    
    std::cout << " ====================== " << std::endl;
    listPtr lp = invert(l1);
    link = lp;

    while(link != NULL)
    {
        std::cout << link->data << std::endl;
        link = link->link;
    }

    return 0;
}

알고리즘 수업 도중 언급된 예제 코드가 머리로는 대충 이해 되지만 실제 동작 코드가 궁금하여 찾아 본 다음 수정해서 올려본다.

list inverting 연산이란 말 그대로 list 를 뒤집는 연산이다. 핵심적인 부분은 invert 함수의 while 부분으로 tail, middle, head 부분을 뒤집어 역순으로 chaining 한다는 부분만 이해하면 된다.