Printing the second half of a linked list in reverse order

Question

I want to print the elements of a linked list, first in their order and then, once I reach the middle, in reverse order (from the last one backwards). For example:

If the elements are: 1 2 3 4 5 6
It should print: 1 2 3 6 5 4
But it's printing: 1 2 3 5 4

Why isn't it printing the last element? How can this be solved?

void reverse()
{
    int c=1;
    node *current,*prev,*temp;
    current=head;
    prev=NULL;
    std::stack<int>s;
    while(current->next!=NULL)
    {
        c++;
        s.push(current->data);
        current=current->next;
    }

    int mid=0;
    if((c%2)==0)
    {
        mid=c/2;
    }
    else
    {
        mid=(c+1)/2;
    }
    current=head;
    for(int i=0;i<mid;i++)
    {
        cout<<current->data<<"\t";
        current=current->next;
    }

    for(int i=mid;i>1;i--)
    {
       std::cout<<s.top()<<"\t";
       s.pop();
    }
    std::cout << '\n';
}

Answer 1

Let's assume that the list contains only one element. In this case this loop

while(current->next!=NULL)
{
    c++;
    s.push(current->data);
    current=current->next;
}

will be executed never and as result the stack will be empty. Moreover the function initially has undefined behavior when the list in turn is empty and hence head is equal to NULL and you may not access current->next data member.

Well now let's assume that the list contains exactly two elements. The loop will be executed only once and the variable c gets value 2. The calculated value of the variable mid will be equal to 1.

So this loop

for(int i=0;i<mid;i++)
{
    cout<<current->data<<"\t";
    current=current->next;
}

executes only one iteration and the first element is outputted.

However the next loop

  for(int i=mid;i>1;i--)
  {
     std::cout<<s.top()<<"\t";
     s.pop();


  }

will; be executed never because its condition i > 1 yields false because mid is equal to 1.

So the program has two wrong loops that should be rewritten.

Below is a demonstrative program that shows how the function can be implemented.

#include <iostream>
#include <stack>

struct node
{
    int data;
    node *next;
} *head = nullptr;

void append( int data )
{
    node **current = &head;

    while ( *current ) current = &( *current )->next;

    *current = new node { data, nullptr };
}

void clear()
{
    while ( head )
    {
        node *tmp = head;
        head = head->next;
        delete tmp;
    }
}

void reverse()
{
    std::stack<int> s;

    for ( node *current = head; current; current = current->next )
    {
        s.push( current->data );
    }

    std::stack<int>::size_type middle = ( s.size() + 1 ) / 2;
    std::stack<int>::size_type i = 0;

    for ( node *current = head; i < middle; i++ )
    {
        std::cout << current->data << '\t';
        current = current->next;
    }

    for ( i = s.size() - i; i != 0; i-- )
    {
        std::cout << s.top() << '\t';
        s.pop();
    }

    std::cout << std::endl;
}

int main() 
{
    const int N = 10;

    for ( int i = 0; i < N; i++ )
    {
        for ( int j = 0; j <= i; j++ ) append( j );
        reverse();
        clear();
        std::cout << std::endl;
    }

    return 0;
}

The program output is

0   

0   1   

0   1   2   

0   1   3   2   

0   1   2   4   3   

0   1   2   5   4   3   

0   1   2   3   6   5   4   

0   1   2   3   7   6   5   4   

0   1   2   3   4   8   7   6   5   

0   1   2   3   4   9   8   7   6   5   

Answer 2

Working code here: http://ideone.com/bbzsSy

2 issues:

• while(current->next!=NULL) should be: while(current!=NULL)
  This way you be sure that you can dereferencing the pointer, plus you also push the last node.

• for(int i=0;i<mid;i++) should be: for(int i=0;i<lastFordward;i++)
  Where lastFordward=(c%2)?mid-1:mid;
  This way avoid to print the mid position twice when c is even.

Answer 3

It's not quite going to compile, but this is somewhat fewer lines:

// assert myList is sorted before called
// if it's not, add       
// std::sort(myList.begin(), myList.end());
// as the first line of the function
void reverseLatterHalf(std::vector& myList)  {
  auto it = myList.begin() + myList.size() / 2;
  std::reverse(it, myList.end());
}

Answer 4

In a typical linked list implementation the last node points to nothing (typically nullptr). Your stop condition for adding the existing elements (current->next!=nullptr) to the stack therefore doesn't include the last element.

Iterating over current would be a better approach as that would stop one after the last node.

Also note that this will have an impact on your mid-point calculation as it is off by one from the start.

Answer 5

This method can work ... declare a function to get the size of the linkList

public int size()
{
    int counter = 0;
    node *nodePtr = head;

    while (nodePtr)
    {
        if (nodePtr->next != null)
        {
            counter++;
        }
    }

    return counter;
}

then if size returned is an even number ...

int c = size()/2;

else ...

int c = (size()+1)/2;

then initialize and array and print them in reverse .... try it out might work :)

Answer 6

In your while loop you are checking if current->next is null you need to check if current is null.

while(current)
{
    c++;
    s.push(current->data);
    current=current->next;
}

You weren't adding the last number into the stack