프로그래밍 면접 문제 5 : Linked List Remove Nodes

이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.

이전글 – 프로그래밍 면접 질문 4 : Find Missing Element

이 문제는 아주 기본적인 문제지만, 버그없이 구현하기가 상당히 까다롭습니다. 연결 리스트에서 주어진 정수 값을 저장하고 있는 모든 노드를 삭제하는 문제입니다.

이 문제를 풀때 고려해야하는 몇가지 상황이 있습니다. 제거해야하는 값을 5라고 해보겠습니다.

작성해야 하는 함수의 입력은 연결 리스트의 헤드(head) 값과 제거할 정수 값입니다. 여기에서 고려해야하는 가장 중요한 사항은 제거해야하는 값이 연결리스트의 헤드인 경우 입니다. 이 경우, 연결리스트의 헤드를 가리키는 포인터를 갱신해야 합니다. 이 때문에, 작성할 함수에서 연결리스트의 포인터의 포인터 또는 포인터를 레퍼런스로 입력 받도록 해야 합니다(또는 헤드를 가리키는 새로운 포인터를 생성해서 함수에서 반환할 수도 있습니다). 이렇게 하지 않으면, 변경된 헤드 포인터가 함수를 호출한 호출자에 적용되지 않습니다. 개인적으로는 좀 더 깔끔하게 코드를 구성할 수 있기 때문에 포인터를 레퍼런스로 전달하는 방법을 더 선호합니다.

정수 5를 저장하고 있는 모든 노드를 제거해 보겠습니다. 먼저 연결 리스트의 처음 부분부터 검색해서 숫자 5가 저장된 노드를 모두 제거하고, 이 과정이 종료되면 숫자 5가 아닌 첫번째 요소(null이 될수도 있습니다)를 가리킬 수  있도록 헤드 포인터를 갱신합니다. 그런 다음, 루프를 시작하고 next 노드에 숫자 5가 저장되어 있는지 확인합니다. 아닌 경우, 포인터를 그 다음 next 노드로 옮겨서 계속 진행합니다. 5이면 next 노드 포인터가 적절하게 그 다음 포인터를 가리키도록 수정하고 5를 저장하고 있는 노드를 삭제합니다. 하지만 새로 설정된 next 노드에서 숫자 5를 저장하고 있고, 포인터를 다음으로 이동시키면 기존에 5를 저장하고 있던 노드를 삭제할 수 없기 때문에 포인터를 앞으로 이동시키지 않습니다. 이는 두개 이상의 연속된 노드를 삭제해야할 때 세심하게 고려해야하는 부분입니다. 다음은 C 코드입니다:

typedef struct Node
{
    int val;
    Node *next;
} Node;
 
void RemoveNodes(Node* &head, int rmv)
{
    while (head != NULL && head->val == rmv)
    {
        Node *temp = head;
        head = head->next;
        free(temp);
    }
    if (head == NULL)
        return;
 
    Node *current = head;
    while (current->next != NULL)
    {
        if (current->next->val == rmv)
        {
            Node *temp = current->next;
            current->next = temp->next;
            free(temp);
        }
        else
        {
            current = current->next;
        }
    }
}

시간 복잡도는 O(N), 공간 복잡도는 O(1)으로 효율적인 해결 방법입니다. 기본 개념에 대한 문제지만 버그없이 코드를 작성하는 것이 쉽지 않기 때문에 개인적으로 특히 이 문제를 좋아합니다.

다음글 – 프로그래밍 면접 문제 6 : Combine Two Strings