Reversing sublist of even numbers

Question

I'm trying to reverse a sublist of even numbers. There seems to be a logical error in code but I'm unable to find it.

    node *sublist_reverse(node *head)
    {
        node *temp=head,*wrking,*wrking_bfr,*node_tobe_ext;
        while(temp!=NULL)
        {
            if(temp->link->data%2==0)
            {
                while(temp->link->data%2==0)
                {
                    if(temp->data%2!=0)
                    {
                        wrking_bfr=temp;
                        wrking=wrking_bfr->link;
                    }
                    node_tobe_ext=wrking->link;
                    wrking->link=node_tobe_ext->link;
                    node_tobe_ext->link=wrking_bfr->link;
                    wrking_bfr->link=node_tobe_ext;
                    temp=wrking->link;
                }
            }
            else
            {
                temp=temp->link;
            }
        }
        return head;
    }

Answer 1

It is not a simple assignment for beginners as you and me.

Your function is incorrect at least because within the function the pointer head is not being changed though a list can start from nodes that contains even numbers, In this case the value of the pointer head will be changed. But this does not occur in your function. There is no statement in the function where the value of the pointer head would be changed.

I can suggest a more general solution. For starters the function accepts the pointer to the head node by reference (through a pointer to it) and also has one more parameter that specifies a predicate. If a subsequence of nodes satisfy the predicate it is reversed. In particularly the predicate can determine for example whether a number stored in a node is even.

Here you are.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct node
{
    int data;
    struct node *link;
} node;

int push_front( node **head, int data )
{
    node *new_node = malloc( sizeof( *new_node ) );
    int success = new_node != NULL;
    
    if ( success )
    {
        new_node->data = data;
        new_node->link = *head;
        *head = new_node;
    }
    
    return success;
}

FILE * display( const node *head, FILE *fp )
{
    for ( ; head != NULL; head = head->link )
    {
        fprintf( fp, "%d -> ", head->data );
    }
    
    fputs( "null", fp );
    
    return fp;
}

void reverse_ranges( node **head, int predicate( int ) )
{
    while ( *head )
    {
        if ( predicate( ( *head )->data ) )
        {
            node **current = head;
            head = &( *head )->link;
            
            while ( *head != NULL && predicate( ( *head )->data ) )
            {
                node *tmp = *current;
                *current = *head;
                *head = ( *head )->link;
                ( *current )->link = tmp;
            }                   
        }
        else
        {
            head = &( *head )->link;
        }
    }
}

int even( int data ) 
{ 
    return data % 2 == 0; 
}

int main(void) 
{
    node *head = NULL;
    
    srand( ( unsigned int )time( NULL ) );

    const int N = 15;

    for ( int i = 0; i < N; i++ )
    {
        push_front( &head, rand() % N );
    }

    fputc( '\n', display( head, stdout ) );
    
    reverse_ranges( &head, even );
    
    fputc( '\n', display( head, stdout ) );

    return 0;
}

The program output might look like

8 -> 10 -> 12 -> 7 -> 5 -> 10 -> 4 -> 8 -> 2 -> 6 -> 7 -> 1 -> 0 -> 4 -> 6 -> null
12 -> 10 -> 8 -> 7 -> 5 -> 6 -> 2 -> 8 -> 4 -> 10 -> 7 -> 1 -> 6 -> 4 -> 0 -> null

I think that the function that frees all the allocated memory of a list will be written by you yourself.

Answer 2

I'm trying to reverse a sublist of even numbers.

From the code presented, it appears that what you're trying to do is reverse every maximal sublist of consecutive even numbers, not just one. Moreover, this is apparently in the context of a singly-linked list, as opposed, say, to an array or a doubly-linked list. Furthermore, I infer from your code that node is defined as a structure type, containing at least members data and link, so maybe

struct node {
    int data;
    struct node *link;
};

typedef struct node node;

With those understandings, it appears that your idea is to scan the list to find the start of a sublist of even numbers, reverse that sublist, then repeat. That yields the nested loop structure presented in your code, and it is a viable way to approach the problem.

Please, someone tell me what is my logical error.

It's unclear what specific issues or misbehaviors you have recognized in your implementation, but here are some that are evident from the code:

• Bad Things happen when the outer loop reaches the end of the list, when the function evaluates

      if(temp->link->data%2==0)
  

  This is because when temp points to the last node, temp->link is not a valid node pointer.

• Bad Things happen when the inner loop reaches the end of the list, too, which occurs when the last element is even. These are the problematic lines:

             node_tobe_ext=wrking->link;
             wrking->link=node_tobe_ext->link;
  

  When wrking points to the last node, node_tobe_ext is not a valid node pointer.

• When the list contains an initial sublist of two or more even numbers, that is not correctly reversed. One can see that this must be the case, because the parity of the first list element is never even checked, and because the function always returns the original head pointer. (If there is an initial sublist of two or more even numbers, then the original head node will not be the head of the final list.)