[HackerRank] Reverse a linked list

Reverse a linked list | HackerRank

Reverse a linked list | HackerRank

 

<문제>

 

input: 첫번째 줄에 테스트할 개수를 입력받고 각 줄마다 들어갈 data를 하나씩 입력받는다.

output: 입력받은 리스트를 reverse하여 출력한다.

 

<코드>

SinglyLinkedListNode* reverse(SinglyLinkedListNode* llist) {
    if(llist==NULL)
        return llist;
    if (llist->next==NULL){
        return llist;
    }
    struct SinglyLinkedListNode* tmp=(reverse(llist->next));
    struct SinglyLinkedListNode* headtmp=tmp;
    while (tmp->next!=NULL){
        tmp=tmp->next;
    }
    tmp->next=llist;
    llist->next=NULL;
    return headtmp;
}

 

<풀이>

이번 문제는 재귀함수를 이용해 풀었다.

먼저 처음에 if문을 통해 만약 llist포인터가 NULL이거나 llist가 가리키는 next가 NULL이면 리스트가 비어있는 것이므로 그냥 llist를 리턴하게 하였다.

if문이 모두 거짓이라면 tmp포인터를 선언하여 next가 가리키는 것을 다시 reverse()함수를 씌워 가리키게 하였고, headtmp 포인터를 선언하여 reverse된 리스트의 head를 가리키고 있는 tmp포인터를 가리키게 하였다. 그리고 while 반복문을 통해 tmp포인터가 NULL을 가리킬 때까지 tmp 포인터가 next에 있는 것을 가리키도록 하였다.

마지막으로 tmp->next=llist;를 통해 next가 llist를 가리키게 하였고, headtmp포인터를 리턴하여 reverse리스트의 head를 리턴하였다.

 

<실행결과>