Программа зависает при реализации связанного списка

Question

Цель этой программы - лучше понять связанные списки. Я должен создать функцию PromoteTarget, которая выполняет следующие действия:

• Просматривает список номеров, и если указанное число не найдено (цель), оно добавляется в конец списка. ,Если список пуст, то цель становится главой.
• Если цель найдена в списке один или несколько раз, то номера целей должны быть выведены в начало списка. Я должен быть в состоянии сделать это без изменения или удаления каких-либо узлов.

Вот мой код:

      void PromoteTarget(Node*& headPtr, int target)
    {

    Node *current = headPtr;
    Node *prevnode = headPtr;
    int count = 0;
    while (current != 0) {
        if (current->data == target) {
            count++;
        }
        current = current->link;
    }
    if (count == 0) {

        Node *newNodePtr = new Node;
        newNodePtr->data = target;
        newNodePtr->link = 0;
        if (headPtr == 0)
            headPtr = newNodePtr;
        else
        {
            Node *cursor = headPtr;

            while (cursor->link != 0)
                cursor = cursor->link;
            cursor->link = newNodePtr;
        }
    }

    if (count > 0) {
        current = headPtr;
        while (current != 0) {
            if (current->data == target) {
                prevnode->link = current->link;
                current->link = headPtr;
                headPtr = current;
            }
            prevnode = current;
            current = current->link;
        }
    }
    }

Это пример того, что я должен получить в качестве вывода:

================================
passed test on empty list
================================
initial: 4  5  
(target: 3)
ought2b: 4  5  3  
outcome: 4  5  3  
================================
initial: 3  4  5  7  4  5  
(target: 5)
ought2b: 5  5  3  4  7  4  
outcome: 5  5  3  4  7  4  
================================
initial: 7  6  4  3  4  5  
(target: 4)
ought2b: 4  4  7  6  3  5  
outcome: 4  4  7  6  3  5  
================================
initial: 6  5  7  5  3  5  6  5  3  
(target: 7)
ought2b: 7  6  5  5  3  5  6  5  3  
outcome: 7  6  5  5  3  5  6  5  3  
================================
initial: 5  
(target: 6)
ought2b: 5  6  
outcome: 5  6  
================================
initial: 5  6  4  4  5  7  
(target: 6)
ought2b: 6  5  4  4  5  7  
outcome: 6  5  4  4  5  7  
================================

Вот что я на самом деле получаю:

================================
passed test on empty list
================================
initial: 4  5  
(target: 3)
ought2b: 4  5  3  
outcome: 4  5  3  

Программа зависает и никогда не выдает мне полный вывод. Исходя из результатов, которые я получаю, у меня довольно хорошее предчувствие, что первая половина моей программы работает так, как задумано. Хотя я могу полностью ошибаться. Если бы мне пришлось угадывать, моя проблема возникает всякий раз, когда я пытаюсь переместить элементы в начало связанного списка. Моя логика выглядит хорошо? Я забыл или пропустил что-то или я совершил глупую ошибку?

Answer 1

Вы можете выполнить обе операции за один проход по связанному списку. Во время самого обхода каждый раз, когда встречается узел с data, равным target, сдвигайте этот узел в начало связанного списка и устанавливайте для логической переменной exists значение true. В конце обхода, если exists == false, тогда добавьте новый узел в конец связанного списка.

Node* createNode(int target)
{
    Node *newNodePtr = new Node;
    newNodePtr->data = target;
    newNodePtr->link = nullptr;
    return newNodePtr;
}

void PromoteTarget(Node*& headPtr, int target)
{
    if (headPtr == nullptr)
        headPtr = createNode(target);
    else
    {
        Node *prev, *curr;
        prev = headPtr;
        curr = headPtr->link;
        bool exists = false;
        while (curr != nullptr)
        {
            if (curr->data == target)
            {
                exists = true;
                prev->link = curr->link;
                curr->link = headPtr;
                headPtr = curr;
                curr = prev->link;
            }
            else
            {
                prev = curr;
                curr = curr->link;
            }
        }

        if (exists == false)
            prev->link = createNode(target);
    }
}