[HackerRank] Compare two linked lists

Compare two linked lists | HackerRank

Compare two linked lists | HackerRank

 

<문제>

input: 첫번째 줄에는 총 테스트 개수를 입력받고, 두번째 줄부터는 linked list를 입력받는다.
input으로 linked list를 입력하는 방법- 첫번째 줄에는 첫번째 linked list의 노드 개수를 입력한다. 
그리고 다음줄에 노드 개수만큼 값을 입력받아 리스트에 저장한다. 
노드 개수만큼 값을 입력받으면 다음으로 비교할 두번째 linked list의 노드 개수를 입력하고, 다음 줄에 노드 개수만큼 입력하여 리스트에 저장한다.

output: 두 linked list를 비교해서 만약 같으면 1, 다르면 0을 출력한다. 그리고 테스트 결과마다 줄을 바꿔서 출력한다. 

 

<코드>

bool compare_lists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {

    SinglyLinkedListNode *p= head1, *q= head2;

    while((p!=NULL) && (q!= NULL))
    {
        if((p->data) != (q->data))
            return 0; 
        p= p->next;
        q= q->next;
    }
    return (p==NULL && q==NULL)? 1:0;
}

 

<풀이>

 각 리스트의 head부터 반복문을 통해 하나씩 비교하다가 중간에 하나 다른 것이 있으면 바로 리턴 0을 하면 되고, 반복문이 끝나고 리스트가 같으면 1을 리턴하면 된다. 하지만 반복문은 linked list 중 하나만 NULL이어도 빠져나오므로 반복문을 빠져나왔을 때 두 개의 리스트 모두 NULL을 가리키고 있어야 1을 리턴하도록 해야한다. 
 이 풀이대로 코드를 짰다. 먼저 head1은 p 포인터, head2는 q 포인터에 저장하였다. while 반복문이 실행되는 동안 if 조건식처럼 p->data와 q->data가 같지 않으면 0을 리턴하고, 같으면 p와 q는 다음 노드를 가리키게 하였다. while 반복문을 빠져나왔을 때 만약 p와 q 모두 NULL을 가리키고 있으면 1을 리턴, 아니면 0을 리턴하여 문제를 풀 수 있었다.

 

<실행결과>