Insert a Node at the Tail of a Linked List

주어진 연결 리스트(Linked List)의 끝에 새로운 노드를 추가하는 알고리즘 문제입니다. 이 문제의 목표는 주어진 연결 리스트에 새로운 노드를 추가하여 연결 리스트를 확장하는 것입니다.

연결 리스트는 데이터 요소(Node)로 이루어진 데이터 구조로, 각 노드는 데이터와 다음 노드를 가리키는 링크(또는 포인터)로 구성됩니다. 연결 리스트의 끝을 나타내는 노드는 다음 노드를 가리키는 링크가 없는 특별한 노드일 수 있습니다.

문제 설명:
문제의 입력으로는 연결 리스트와 추가할 데이터가 주어집니다. 연결 리스트의 끝에 추가할 데이터를 가지는 새로운 노드를 만들고, 이를 연결 리스트에 추가해야 합니다.

알고리즘 절차:

추가할 데이터를 가지는 새로운 노드를 생성합니다.
연결 리스트가 비어 있는지 확인합니다. 비어 있다면 새로운 노드를 시작 노드로 지정합니다.
연결 리스트가 비어 있지 않다면, 연결 리스트의 끝까지 이동합니다. 이동할 때, 현재 노드의 다음 노드를 따라가며 끝까지 이동합니다.
끝에 도달한 후, 현재 노드의 다음 노드를 새로운 노드로 설정합니다.
이렇게 하면 새로운 노드가 연결 리스트의 끝에 추가되고, 연결 리스트가 확장됩니다. 추가된 노드는 연결 리스트의 마지막 노드가 되며, 다음 노드를 가리키는 링크는 없으므로 끝을 나타냅니다.

이 알고리즘은 연결 리스트가 비어 있는 경우와 비어 있지 않은 경우를 모두 처리할 수 있어야 합니다. 따라서 시작 노드를 지정하고, 연결 리스트가 비어 있지 않을 때에만 끝까지 이동하여 노드를 추가하는 부분을 주의 깊게 처리해야 합니다.

 

SinglyLinkedListNode* insertNodeAtTail(SinglyLinkedListNode* head, int data) {
    SinglyLinkedListNode* newNode = new SinglyLinkedListNode(data);
    
    if(head == nullptr){
        head = newNode;
    }
    else{
        SinglyLinkedListNode* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }
    return head;
}

Queue 사용

SinglyLinkedListNode* insertNodeAtTail(SinglyLinkedListNode* head, int data) {
    
    
    SinglyLinkedListNode* newNode = new SinglyLinkedListNode(data);

    if (head == nullptr) {
        head = newNode;
    } else {
      queue<SinglyLinkedListNode*> q;
      q.push(head);
    
    while(!q.empty()){
        SinglyLinkedListNode* current = q.front();
        q.pop();
        
        if(current->next == nullptr){
            current->next = newNode;
            break;
        }
       else if(current->next){
            q.push(current->next);
       		 }
    	}
    }

    return head;
}