Средний узел односвязного списка

Question

Я нашел этот код для печати среднего узла списка на C++, но я не понимаю код ... Кто-нибудь может мне это объяснить?

Type& findMiddleNode() 
{ 
    int check = 0; 
    nodeType *current; 
    nodeType *mid; 

    current = first; 
    mid = first; 

    while (current != NULL) 
    { 
     current = current->link; 
     check = (check + 1) % 2; 

     if (check == 0) 
      mid = mid->link; 
    } 

    return mid->info; 
} 

PD: Этот код работает идеально, но я не понимаю! Кто-то поможет мне понять это. Благодаря!

Answer 1

Основная идея заключается в том, чтобы переместить два указателя B и A по списку, но с B движется только половину скорости А.

Изложение

check = (check + 1) % 2; 

& hellip; дает check значения 0, 1, 0, 1 и т. д., которые используются для перемещения B только каждый второй раз A.

Эта же идея - один из возможных (и ожидаемых) ответов на вопрос о проверке того, содержит ли связанный список один цикл. В этом случае быстро перемещающийся указатель догонит медленный после того, как оба вошли в цикл.

---

Более простой способ сделать то же самое, только с приблизительно одной и той же работы, затраченной программой, чтобы (1) подсчитать количество узлов п, и (2), начиная с самого начала снова, перейти на номер узла n/2.

Шаг (1) перемещает указатель п раз, как и выше, и стадию (2) перемещает указатель п/2 раза, как B выше.