[해커랭크] Inserting a Node Into a Sorted Doubly Linked List (C++)

문제 링크: www.hackerrank.com/challenges/insert-a-node-into-a-sorted-doubly-linked-list/problem

Inserting a Node Into a Sorted Doubly Linked List | HackerRank

1. 주의할 점

- List의 가장 앞 혹은 뒤에 추가되는 경우를 조심한다

 

2. 구현

- 2가지의 방법을 통해 구현해봤다

[List 생성]

- DoublyLinkedList* list라는 새로운 리스트를 생성한다

- 추가되었는지의 여부를 Add 변수를 통해 확인한다(초기화는 False로)

- 파라미터로 받은 Head가 Null을 가리킬때까지 While문을 수행한다

- 현재 데이터가 새로 추가하려는 data보다 크기가 크거나 같고 Add의 값이 false라면 list에 data를 넣고 Add의 값을 True로 바꾼다. 이후, list에 현재 데이터를 추가한다

- 현재 데이터가 새로 추가하려는 data보다 작고 tail이 아니라면, list에 현재 데이터를 추가한다. 만약 tail이라면 현재 데이터를 넣은 후, 가장 뒤에 data를 추가한다

- 위의 조건이 끝났다면, head를 다음 node를 가리키도록 옮긴다

- While문이 끝나면 List->head를 넘겨서 리스트 전체를 넘긴다

DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* head, int data) {
    DoublyLinkedList* list = new DoublyLinkedList();
    int cur;
    bool add = false;
    while(head){
        cur = head->data;
        if(cur>=data){      //전에 추가
            if(!add){
                list->insert_node(data);
                add=true;
            }
            list->insert_node(cur);
        }
        else{       //cur < data
            list->insert_node(cur);
            if(head->next ==nullptr){	//가장 뒤에 추가
                list->insert_node(data);               
                break;
            }
        }
        head = head->next;
    }
    return list->head;
}

 

[넘겨받은 Head만 사용]

- 앞의 코드와 원리는 비슷하나, data를 추가하면 while문을 종료하도록 설정한다

- 추가적인 조건은 2가지가 있다

- 첫 번째로는 if(data<=cur)일 때, 가장 앞에 data가 추가될 때와 중간에 추가될 때를 유의한다. 중간에 추가하는 경우, 이전 Node의 다음을 추가되는 data 노드를 향하도록 바꾼다.

- 두 번째로는 head가 현재 가장 앞부분을 안가르킬 수 있으므로, 가장 앞부분을 가리키도록 While문을 수행한다

DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* head, int data) {
    int cur;
    while (head) {
        cur = head->data;
        if (data <= cur) {
            DoublyLinkedListNode *node = new DoublyLinkedListNode(data);
            node->prev = head->prev;
            node->next = head;
            if(head->prev!=nullptr)
                head->prev->next = node;
            head->prev = node;
            break;
        }
        else {
            if (head->next != nullptr) {
                head = head->next;
            }
            else {
                DoublyLinkedListNode *node = new DoublyLinkedListNode(data);
                node->prev = head;
                node->next = head->next;
                head->next = node;
                break;
            }
        }
    }
    while (head->prev != nullptr) {
        head = head->prev;
    }
    return head;
}