Подсчет элементов зацикленного односвязного списка C(СИ)

Question

Дан односвязный список, элементы которого содержат в себе лишь указатели на следующие элементы списка. Известно, что в один момент список зациклиться. Список может быть любой длинны и зациклиться может на любой элемент (хоть первый, хоть предпоследний). Задача: вернуть количество элементов цикла. Пробовал следующим образом:

#include <stddef.h>

typedef struct node_t Node;
struct node_t {
    Node* next;
};

typedef enum {false, true} bool;

typedef struct BINTREE tree_t;
struct BINTREE{
    tree_t *rightTale;
    tree_t *leftTale;
    int list_pos;
    Node *nodePtr;
    bool frstLoopTale;
};

tree_t *addtree(tree_t *p, Node* currNodeTale);

long list_size = 0;

int loop_size(Node* node) {
    tree_t *root = NULL;
    int frstLoopTale;
    while(!(root->frstLoopTale)){
        list_size++;
        root = addtree(root, node);
        node = node->next;
}
    frstLoopTale = root->list_pos;
    free(root);
    return list_size - frstLoopTale;
}

tree_t *addtree(tree_t *p, Node* currNodeTale){
    if(p==NULL){
        p = (tree_t *) malloc(sizeof(tree_t));
        p->list_pos = list_size;
        p->leftTale = p->rightTale = NULL;
        p->nodePtr = currNodeTale;
        p->frstLoopTale = false;
    }
    else if(currNodeTale == p->nodePtr)
        p->frstLoopTale = true;
        else if(currNodeTale < p->nodePtr)
        p->leftTale = addtree(p->leftTale, currNodeTale);
    else
        p->rightTale = addtree(p->rightTale, currNodeTale);
    return p;
}

Есть предположение, что я неверно очищаю бинарное дерево функцией free() в main. А так же мне кажется, что возможно сделать это гораздо проще. Прошу прощения за возможно глупые вопросы и заранее благодарю за ответ.

Answer 1

Вот пример для моего варианта — "Чтоб попасть в цикл, обычно используют 2 указателя — один идет с шагом 1, второй — с шагом 2. Когда они указывают на один и тот же элемент — вы в цикле. Дальше просто пробежать его по кругу и посчитать количество элементов..."

Не нужна память O(N) для запоминания пройденных узлов. Время работы, понятно, O(N).

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

typedef struct node_t Node;
struct node_t {
    Node* next;
};

int main(int argc, const char * argv[])
{
    srand(time(0));
    int C = rand() + 20;   //  Размер цикла
    int T = rand();        //  Размер хвоста

    // Строим цепь
    Node * n = malloc(sizeof(Node)*(T+C));

    for(int i = 0; i < T+C-1; ++i)
        n[i].next = &n[i+1];

    n[T+C-1].next = &n[T];

    // Ищем точку в цикле
    Node * p = n, * p2 = n;
    do
    {
        p = p->next;
        p2 = p2->next->next;
    } while(p != p2);

    //  Ищем длину цикла
    int cnt = 1;
    for(;(p = p->next) != p2; cnt++);

    printf("%d vs %d\n",C,cnt);

}

БЛОГ НА HUSL

Подсчет элементов зацикленного односвязного списка C(СИ)

Ответы (1 шт):