Печать середины связанного списка в случае четного количества элементов

Question

Я знаю, как печатать середину данного связанного списка, принимая два указателя, которые перемещаются с разной скоростью. Первый указатель перемещается на один, а второй указатель перемещается на две позиции. Теперь, если связанный список содержит четное количество узлов, т. Е. Скажем, 4 узла, то, который будет технически быть посередине. Кроме того, условие, которое я использую в то время цикла для печати является,

fastptr = head; 
slowptr = head; 

while (fastptr->next->next != NULL && slowptr->next != NULL) 
{ 
    slowptr = slowptr->next; 
    fastptr = fastptr->next->next; 
} 

В этом случае, если я запускаю приведенный выше код вручную один раз, а затем, код остановится, когда slowptr находится на втором узле и fastptr находится на 3 узлах. Это верно?

Answer 1

Это было бы более ясным и видимым рассмотрим следующую показательной программы

#include <iostream> 

int main() 
{ 
    const size_t N = 10; 
    int a[N] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 

    while (true) 
    { 
     std::cout << "\nEnter the size of the sub array less than or equal to " 
        << N << " (0 - exit): "; 

     size_t n = 0; 
     std::cin >> n; 

     if (!n) break; 

     if (N < n) n = N; 

     size_t i = 0; 
     for (size_t j = 0; j < n && ++j < n && ++j < n;) i++; 

     for (size_t j = 0; j < n; j++) std::cout << a[j] << ' '; 
     std::cout << std::endl; 
     std::cout << a[i] << std::endl; 
    }  
} 

Его выход

Enter the size of the sub array less than or equal to 10 (0 - exit): 10 
0 1 2 3 4 5 6 7 8 9 
4 

Enter the size of the sub array less than or equal to 10 (0 - exit): 9 
0 1 2 3 4 5 6 7 8 
4 

Enter the size of the sub array less than or equal to 10 (0 - exit): 8 
0 1 2 3 4 5 6 7 
3 

Enter the size of the sub array less than or equal to 10 (0 - exit): 7 
0 1 2 3 4 5 6 
3 

Enter the size of the sub array less than or equal to 10 (0 - exit): 6 
0 1 2 3 4 5 
2 

Enter the size of the sub array less than or equal to 10 (0 - exit): 5 
0 1 2 3 4 
2 

Enter the size of the sub array less than or equal to 10 (0 - exit): 4 
0 1 2 3 
1 

Enter the size of the sub array less than or equal to 10 (0 - exit): 3 
0 1 2 
1 

Enter the size of the sub array less than or equal to 10 (0 - exit): 2 
0 1 
0 

Enter the size of the sub array less than or equal to 10 (0 - exit): 1 
0 
0 

Enter the size of the sub array less than or equal to 10 (0 - exit): 0 

Таким образом, вы можете увидеть себя, какой элемент будет outputed, когда есть четное или нечетное элементов в массиве.

Как переписать код для списка?

Это может выглядеть следующим образом

node *slowptr = head; 

for (node * fastptr = head; 
     fastptr && (fastptr = fastptr->next) && (fastptr = fastptr->next);) 
{ 
    slowptr = slowptr->next; 
} 

Этот цикл можно записать еще проще, если вы будете проверять перед циклом, что head не равна NULL

Например

node *slowptr = head; 

if (slowptr) 
{ 
    for (node * fastptr = head; 
      (fastptr = fastptr->next) && (fastptr = fastptr->next);) 
    { 
     slowptr = slowptr->next; 
    } 
} 

Что касается цикла, который вы показали, то это неверно

while (fastptr->next->next != NULL && slowptr->next != NULL) 

fastptr и fastptr->next каждый может быть равен NULL. Таким образом, код имеет неопределенное поведение.

Answer 2

Теперь, если связанный список содержит четное количество узлов, то есть, скажем, 4 узла, то какой из них технически будет посередине?

Может быть:

• второй
• третий
• ни, даже списки длины нет нет среднего

... В зависимости от конкретного определения «средний». Обратитесь к своему назначению за правильной интерпретацией или используйте любое значение, которое наиболее удобно, если оно не указано.

В этом случае, если я запустил вышеуказанный код вручную один раз, тогда код остановится, когда slowptr находится на втором узле, а fastptr - на 3 узлах. Это верно?

Да. (Предполагая, что «3 узла» вы имеете в виду «третий узел», а не «четвертый узел», что было бы, если бы вы использовали систему индексирования с нулевым индексом)

Answer 3

Вы можете выбрать 2-й или 3-й узел должен быть средним (если число узлов равно 4). Но в большинстве случаев вы увидите, что второй узел обрабатывается как средний узел. Вы можете видеть следующий код, поскольку ваш код может сбой, например если есть 3 узла. После одной итерации цикла fastptr будет указывать на последний узел, а fastptr->next->next - сбой.

fastptr=head; 
slowptr=head; 
while(fastptr->next!=NULL)//ie continue until fastptr is at lastnode 
{ 
    fastptr=fastptr->next; 
    if(fastptr->next==NULL)//ie last node 
    break; 
    fastptr=fastrptr->next; 
    slowptr=slowptr->next; 
    } 
    //slowptr is pointing to middle node. 

РЕДАКТИРОВАТЬ: проверить, пуст ли список заранее.