Связанные понятия списка - PullRequest
Новая
       58

Связанные понятия списка

0 голосов
/ 22 марта 2020

Значение узла в *node=*(node->next), если узел является последним элементом в связанном списке?

Значение узла будет равно NULL или нет?

Учитывая односвязный список состоящий из N узлов. Задача состоит в том, чтобы удалить дубликаты (узлы с дублирующимися значениями) из заданного списка (если существует). Примечание. Старайтесь не использовать дополнительное пространство. Ожидаемая сложность времени O (N). Узлы расположены в отсортированном виде.

Это решение не сработало для контрольного примера 2 2 2 2 2 (пять узлов с одинаковыми значениями). 

Node *removeDuplicates(Node *root)
{
    if(root->next==NULL)
        return root;

    Node * t1=root;
    Node* t2=root->next;
    while(t2!=NULL)
    {
        if(t1->data==t2->data)
        {
            *t2=*(t2->next);
        }
        else
        {
            t1=t1->next;
            t2=t2->next;
        }
    }
    return root;
}

Это сработало: 

Node *removeDuplicates(Node *root)
{
    if(root->next==NULL)
        return root;

    Node * t1=root;
    Node* t2=root->next;
    while(t2!=NULL)
    {
        if(t1->data==t2->data)
        {
            if(t2->next==NULL)
            {
                t1->next=NULL;
                t2=NULL;
            }
            else
            {
                *t2=*(t2->next);
            }
        }
        else
        {
            t1=t1->next;
            t2=t2->next;
        }
    }
    return root;
}

1 Ответ

0 голосов
/ 22 марта 2020

Обычно я бы не стал публиковать полный код чего-то, что было бы домашней работой, но я не был уверен, как правильно сформулировать все пункты. Я также не скомпилировал и не запустил это, потому что я не хотел создавать свой собственный класс Node.

Сначала мы можем поговорить об алгоритме. Если ваш односвязный список уже отсортирован и NULL завершен, то, по сути, у нас есть текущий узел, указывающий на узел в списке, и путевой узел (nextNode), который идет по списку. Главное, что нам нужно сделать, это обновить указатели, чтобы они указывали на следующий узел, как только мы нашли не дубликат.

В приведенном ниже коде я также добавил проверки NULL, что невероятно важный. Привыкайте точно знать, в каком состоянии могут находиться ваши переменные, так как легко случайно вызвать метод с нулевым указателем, что приведет к тому, что программа обработает sh. 

Node* removeDuplicates(Node* root)
{
  // Check that root isn't null before checking that its next pointer is also not NULL
  if (root == NULL || root->next == NULL)
    return root;

  // Set up our current node and the travel node
  Node* currentNode = root;
  Node* nextNode = root->next;

  // Until we've reached the end of the singly linked list
  while (nextNode != NULL)
  {
    // Find the next node that isn't a duplicate
    // Also check that we don't reach the end of the list
    while (nextNode->data == currentNode->data && nextNode != NULL)
      nextNode = nextNode.next;

    // Update the current node's next pointer to point to the travel node
    currentNode->next = nextNode;

    // Update the current node to its next for the next iteration
    currentNode = nextNode;

    // Update the next node being careful to check for NULL
    nextNode = nextNode == NULL ? NULL : nextNode->next;
  }

  return root;
}

Это не единственный способ справиться с этой проблемой. Реорганизуя, когда вы делаете определенные проверки и ассоциации, вы можете отменить некоторые проверки NULL или сделать программу более понятной. Это только одно из возможных решений.

...