c++ - 在偶数个元素的情况下打印链表的中间

Question

我知道如何通过采用两个以不同速度移动的指针来打印给定链表的中间部分。第一个指针移动一个位置，而第二个指针移动两个位置。现在，如果链表包含偶数个节点，也就是说，假设有 4 个节点，那么从技术上讲，哪一个节点将位于中间。另外，我在 while 循环中用于打印的条件是，

fastptr = head;
slowptr = head;

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

在这种情况下，如果我手动运行一次上述代码，那么当 slowptr 位于第二个节点并且 fastptr 位于第三个节点时，代码将停止。它是否正确？

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

所以你可以自己看看当数组中有偶数或奇数元素时，输出什么元素。

如何重写列表的代码？

它可以看起来像下面这样

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。所以代码有未定义的行为。