Найти цикл в односвязном списке

Опубликовано Sep 22, 2011 в Связанные списки | 6 коммент.


Необходимо написать функцию, которая бы проверила односвязный список, заданный указателем на первый элемент, на наличие зацикливания.

 bool CheckLinkedList(LinkedListNode *firstItem)
{
  //ваш код
}
1 Цель задания проверка навыков алгоритмического мышления
2 Время выполнения 30 минут
3 Формат выполнения код пишется на компьютере/бумаге по желанию, без доступа к документации

Критерии оценки FulcrumWeb:

Кандидат должен продемонстрировать знания стандартных структур данных и умение придумать и реализовывать необходимый алгоритм.

Ожидаемые вопросы:

  1. Можно ли добавить в структуру данных узла необходимое для работы этой функции поле?
  2. Можно ли выделить дополнительную память необходимого размера?
  3. Есть ли среди полей узла списка поле, содержащее заведомо уникальные данные?

Оценка результатов:

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

 

Для начинающего программиста вопросы, связанные с использованием дополнительных допущений, приемлемы. Годится любое работоспособное решение. Лучше, если оно не основано на специфической структуре полей узла и предположениях о данных в этих полях. Хотя может, это и лучше, чем выделять дополнительно память под весь список?

 

От программиста с опытом мы не ожидаем вопросов, так как задача имеет решение для ситуации, когда на все приведенные вопросы дается отрицательный ответ.


6 Коммент. : “Найти цикл в односвязном списке”

  1. begemot says:
    bool CheckLinkedList(NODE * pFirstItem)
    {
    NODE * pNode1= NULL, *pNode2 = NULL;
     
    for (pNode1 = pFirstItem; pNode1->pNext !=NULL; pNode1 = pNode1->pNext)
    {
    	for(pNode2 = pFirstItem; pNode1 != pNode2; pNode2 = pNode2->pNext)
    	{
    		if (pNode1->pNext == pNode2)
    			return true;
    	}
     
    }
    return false;
    }
    • Галина says:

      Понятная простая идея алгоритма, почти правильно. Не справляется только с ситуацией, когда цикл образуется из ссылки на самого себя. Например, если зациклить список так:

      head->next->next = head->next;
      • begemot says:

        Тогда так

        bool CheckLinkedList(NODE * pFirstItem)
        {
        	NODE * pNode1= NULL, *pNode2 = NULL;
         
        	for (pNode1 = pFirstItem; pNode1->pNext !=NULL; pNode1 = pNode1->pNext)
        	{
        		if (pNode1->pNext == pNode1)
        			return true;
        		for(pNode2 = pFirstItem; pNode1 != pNode2; pNode2 = pNode2->pNext)
        		{
        			if (pNode1->pNext == pNode2)
        				return true;
        		}
         
        	}
         
        	return false;
         
        }
  2. Как то так))
    Список по ходу прохождения инвертируется. Если мы пришли в начало списка, то цикл есть. Если пришли в конец, то цикла нет. Потом список опять инвертируем. Время работы О(n).

    bool CheckLinkedList(NODE * pFirstItem)
    {
    	NODE * pNode = pFirstItem->next;
    	NODE * pPrev = pFirstItem;
    	pPrev->next = NULL;
    	while((pNode!=pFirstItem)&&(pNode!=NULL))
    	{
    		//инвертируем список
    		NODE* tmp = pNode->next; 
    		pNode->next = pPrev;
    		pPrev = pNode;
    		pNode = tmp;
    	};
     
    	if(pNode == pFirstItem)
    	{
    		//пришли в начало
    		//инвертируем список
    		pNode = pFirstItem->next;
    		pPrev = pFirstItem;
    		pPrev->next = NULL;
    		while(pNode!=pFirstItem)
    		{
    			NODE* tmp = pNode->next; 
    			pNode->next = pPrev;
    			pPrev = pNode;
    			pNode = tmp;
    		};
    		pNode->next = pPrev;
     
    		return true;
    	}
    	else
    	{
    		//пришли в конец
    		//инвертируем список
    		pNode = pPrev;
    		pPrev = NULL;
    		while(pNode!=NULL)
    		{
    			NODE* tmp = pNode->next; 
    			pNode->next = pPrev;
    			pPrev = pNode;
    			pNode = tmp;
    		};
     
    	};
     
    	return false;
    }
  3. Ольга says:

    А если цикл не в том, что последний элемент указывает на начальный, а, скажем, 20-ый на 11-ый? ваши алгоритмы не найдут, когда конец списка.

  4. Дмитрий says:
    struct LinkedListNode
    {
        int value;
        LinkedListNode *next;
    };
     
    bool CheckLinkedList(LinkedListNode *firstItem)
    {
        LinkedListNode *match = firstItem;
     
        LinkedListNode *curr = firstItem->next;
        while (curr->next != 0 && curr->next != match)
        {
            curr = curr->next;
        }
        if (curr->next != 0)
            return false;
        else
            return true;
    }

Оставить комментарий

Ваш адрес email не будет опубликован.


*