[HackerRank] Find Merge Point of Two Lists / Reverse a doubly linked list

# Find Merge Point of Two Lists (Linked Lists)

[문제]

 

[코드]

int findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    SinglyLinkedListNode* temp1 = head1, *temp2 = head2;
    
    while(temp1 != temp2) {
        temp1 = (temp1 == NULL) ? head2 : temp1->next;
        temp2 = (temp2 == NULL) ? head1 : temp2->next;
    }
    return temp1->data;
}

 

[코드설명]

각 포인터를 동시에 한 단계씩 이동시키면 둘 사이의 간격은 리스트의 크기 차이만큼 난다.

이때 먼저 NULL에 도달한 포인터를 반대 리스트의 head로 변경하고 이동시키면 리스트 크기의 차이에 의해서 벌어진 간격이 좁혀진다.

이 때문에 두 포인터가 한 바퀴를 선회했을 때 두 번째 turn에서 merge pointer에서 만날 수 있게 된다.

 

각각 temp1과 temp2를 선언하고 두 포인터로 리스트를 선회하여 merge pointer를 찾았다.

 

[채점 결과]

 

 

 

 

 

# Reverse a doubly linked list (Linked Lists)

[문제]

 

[코드]

DoublyLinkedListNode* reverse(DoublyLinkedListNode* llist) {
    DoublyLinkedListNode *temp = NULL;
    if(llist){
        do {
            temp = llist;
            llist = llist->next;
            temp->next = temp->prev;
            temp->prev = llist;
        } while(llist);
    }
    return temp;
}

 

[코드설명]

doubly linked list를 reverse하는 문제다.temp에 llist를 담고, llist를 next로 넘겨서 temp의 prev와 next를 재연결했다.temp의 next에 prev를 연결하고 나면, prev에 원래의 next를 연결할 수 없으므로 llist를 사용했다.llist가 NULL이 된다면 while문을 빠져나와서 이전 노드인 temp를 return한다.

 

[채점 결과]