Printing middle of a linked list in case of even number of elements

Question

I know how to print the middle of a given linked list by taking two pointers which move at different speeds. First pointer move by one whereas second pointer move by two positions. Now, in case the linked list contains even number of nodes, that is, let's say 4 nodes, then, which one will technically be the middle. Also, the condition that I am using in the while loop for printing is,

fastptr = head;
slowptr = head;

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

In this case, if I run the above code manually once, then, the code will stop when the slowptr is at second node and fastptr is at 3 node. Is this correct?

Answer 1

1) For those who are visiting this question now , if you consider no of elements =4

• if you consider 2 as middle element then condition should be

   while(fast_ptr->next->next != head) 
  

• if you consider 3 as middle element , then condition should be

   while(fast_ptr != head)
  

2) Also for odd elements condition is :

 while(fast_ptr->next != head)

So together 1) and 2

// for 2 as middle element
while(fast_ptr->next != NULL && fast_ptr->next->next != NULL)
{
   fast_ptr = fast_ptr->next->next;
   slow_ptr = slow_ptr->next;
 }
 printf("The middle element is [%d]\n\n", slow_ptr->data); `

or

// for 3 as middle element
while (fast_ptr != NULL && fast_ptr->next != NULL)
    {
        fast_ptr = fast_ptr->next->next;
        slow_ptr = slow_ptr->next;
    }
    printf("The middle element is [%d]\n\n", slow_ptr->data);

Generally 2nd case , 3 as middle element is used.

Answer 2

That it would be more clear and visible consider the following demonstrative program

#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;
    }       
} 

Its output is

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

So you can see yourself what element will be outputed when there are even or odd elements in the array.

How to rewrite the code for a list?

It can look the following way

node *slowptr = head;

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

This loop can be written even simpler if you will check before the loop that head is not equal to NULL

For example

node *slowptr = head;

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

As for the loop you showed then it is wrong

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

fastptr and fastptr->next each can be equal to NULL. So the code has undefined behaviour.

Answer 3

You could choose 2nd or the 3rd node to be middle(if number of nodes are 4).But most of the times you'll see second node being treated as middle node.You can see the following code as your code might crash for e.g. if there are 3 nodes.After one iteration of the loop,fastptr will be pointing to last node and fastptr->next->next will crash.

 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.

EDIT:Do check if list is empty beforehand.

Answer 4

Now, in case the linked list contains even number of nodes, that is, let's say 4 nodes, then, which one will technically be the middle?

Could be:

• the second one
• the third one
• neither, even length lists have no middle

... Depending on your specific definition of "middle". Refer to your assignment for the correct interpretation, or use whatever meaning is most convenient if it doesn't specify.

In this case, if I run the above code manually once, then, the code will stop when the slowptr is at second node and fastptr is at 3 node. Is this correct?

Yes. (Assuming by "3 node" you mean "the third node" and not "the fourth node", which is what it would be if you're using a zero-based indexing system)