[HackerRank] Print in Reverse / Delete a Node

# Print in Reverse (Linked Lists)

[문제]

 

[코드]

void reversePrint(SinglyLinkedListNode* llist) {
    SinglyLinkedListNode *two = NULL, *three, *temp;
    
    if(!llist) return;
    do{
        three = two;
        two = llist;
        llist = llist->next;
        two->next = three;
    } while(llist);
    
    for(temp = two; temp; temp = temp->next)
        cout << temp->data << endl;
}

 

[코드설명]

연결리스트를 거꾸로 출력하는 문제다.

해당 문제를 해결하기 위해 현재 링크의 연결을 끊고 반대로 연결하는 작업을 했다.

그 후 변경된 링크 포인터를 이용해서 연결리스트의 data를 출력했다.

연결리스트를 reverse하기 전에 llist가 NULL이라면 아무 작업도 하지 않아도 되므로 함수를 종료한다.

 

링크를 재연결하기 위해 two와 three라는 포인터 변수를 추가했고, 각각의 변수는 다음 링크를 따라 해당 포인터를 가지게 된다.

포인터 변수 two가 링크를 재연결해야 하는 노드이므로 two->next가 three의 값을 가지게 하여 반대로 연결했다.

그리고 llist가 NULL인지 확인하고 해당 과정을 반복하게 된다.

llist가 NULL이면 그 다음으로 더이상 노드가 없다는 뜻이므로 반복문을 종료한다.

포인터 변수 temp를 사용해서 변경된 헤드 포인터를 받아오고, 링크를 따라 data의 값을 출력한다.

 

[채점 결과]

 

 

 

 

 

# Delete a Node (Linked Lists)

[문제]

 

[코드]

SinglyLinkedListNode* deleteNode(SinglyLinkedListNode* llist, int position) {
    SinglyLinkedListNode *prev, *node = llist;
    
    if(position==0)
    {   
        llist = llist->next;
        free(node);
    }
    else
    {
        int i = 0;
        while(i != position)
        {
            prev = node;
            node = node->next;
            i++;
        }
        prev->next = node->next;
        free(node);
    }
    return llist;
}

 

[코드설명]

연결리스트에서 지정한 위치에 있는 노드를 삭제하고, 새로운 헤드 노드의 포인터를 반환하는 문제다.

연결리스트의 노드 삭제 같은 경우 2가지 경우를 고려했다.

    ① 삭제하려는 노드가 헤드 노드인 경우

    ② 삭제하려는 노드가 헤드 노드가 아닌 경우

 

먼저 ①의 경우 노드 삭제 후에 llist->next가 새로운 헤드 노드가 된다.

새로운 헤드 노드를 반환하기 위해 llist의 값을 llist->next로 변경해야 한다.

그전에 position 0의 노드를 삭제하기 위해서 llist의 값을 따로 담아두어야 할 필요가 있다.

소스코드 상에서 삭제하려고 하는 노드가 node에 이미 담겨 있으므로 llist를 변경하고 node를 해제한다.

 

다음으로 ②의 경우 노드 삭제 후에도 헤드 노드에는 변함이 없다.

다만 삭제하려고 하는 노드를 직접 찾아가야 한다.

노드 삭제 후에는 앞뒤의 노드를 연결시켜 줘야 하므로 이전 노드의 데이터도 필요하다.

소스코드 상에서 이전 노드는 prev에 현재 노드는 node에 담았다.

position 0부터 시작해서 삭제하려고 하는 positoin에 도달할 때까지 while loop이 실행된다.

삭제하고자 하는 노드의 position에 도달하면 prev->next에 node->next 값을 대입해서 앞뒤로 연결시켜 준다.

연결이 끝나면 node를 해제한다.

 

① 또는 ②의 과정을 거친 후에 리스터 포인터인 llist를 반환한다.

 

[채점 결과]