단방향 연결리스트 반대로 뒤집기.

 1->2->3->null 이렇게 연결되어있는 리스트가 있다고 하자. (이 때 Head : 1)

이 리스트의 내용을 반대로 뒤집을 것이다.

뒤집으면 3->2->1->null이 된다. (이 때 Head : 3)

※ 양방향으로 연결되어있지 않다.

 

void Revers()
{
    if(pHead == NULL)
    {
        printf("데이터가 존재하지 않습니다. \n");
        return;
    }
 
    int Count = DataLen - 1;
 
    Node* pNode = pHead;
    Node* pPrev;
    Node* pTemp;
 
    while(pNode->pNext != NULL)
        pNode = pNode->pNext;
    
    pTemp = pNode;
 
    while( Count > 0 )
    {
        pNode = pHead;
        for(int i = 0; i < Count; i++)
        {
            pPrev = pNode;
            pNode = pNode->pNext;
        }
        pNode->pNext = pPrev;
        Count--;
    }
    pPrev->pNext = NULL;
    pHead = pTemp;
}

방법은 생각해보면 간단하다.

현재 노드가 가리키는 포인터를 반대 방향의 노드를 향하게 하면 되는 일이다.

Head에 접근하여 순서대로 끝 노드까지 접근하자.

현재 끝 노드는 null를 가르키고 있다.

이 노드의 포인터를 반대 방향의 노드에 가르켜야 한다.

여기서 문제가 생긴다.

1. 각 노드의 포인터 방향을 모두 바꾼다고 했을 때 1은 null을 가르켜야 한다.

하지만 1은 Head이다. 방향이 바뀐다면 3이 Head가 될 필요가 있다.

그러면 포인터의 방향을 바꿔주는 작업을 하기전에 끝 노드에 접근하여 그 노드를 가르킬 노드를 임시로 생성해줄 필요가 있다.

그 부분이 15,16행이다.

15,16행은 끝 노드로 접근하는 과정이고 while이 끝나게 되면 pNode는

끝 노드를 가르킨채 반복문에서 빠져나오게 된다.

이때 18행에서 임시로 변수를 생성해주고 그 변수가 끝 노드를 가르키도록 하면 된다.

※ Head를 처음부터 바꾸지 않는다.

각각의 노드들의 포인터를 바꿔줘야 하는데,

한 번에 모든 노드들의 방향을 바꿀수 없기 때문이다.

노드 하나의 포인터를 바꿔주면 다시 처음부터 노드에 접근하여 포인터 방향이 바뀌지 않은 노드까지

이동 후 포인터 방향을 바꿔준다. 모든 포인터 방향이 바뀔때까지 이 작업을 반복한다.

모든 포인터의 방향이 바뀌었을 때 Head에 임시 변수를 대입하면 모든 작업은 끝나게 된다.

pNode를 3까지 접근시켜 3의 포인터를 null이 아니라 2를 가르키게 하자.

그러면 2와 3은 서로를 가르키게 된다.

그러면 다시 pNode를 2까지 접근 시키고 2의 포인터를 1을 가르키게 하자.

pNode를 1에 접근시켜 1의 포인터를 null을 가르키게 하자.

이제 Head를 3으로 옮기자 3의 위치는 임시변수인 Temp가 가지고 있다.

※ DataLen은 전역변수로 리스트에 데이터가 하나 추가될때마다 1씩 증가한다.

즉, 리스트에 데이터가 3개 존재한다면 DataLen은 3이된다.