Отправлено: 25.06.18 12:55. Заголовок: Рекурсивное Обращение (реверсия) односвязного списка.

Достаточно часто начинающим программистам в качестве учебного задания предлагается рекурсивно обратить (реверсировать) односвязный список. Вот, например, подобный вопрос на Stackoverflow Reverse single linked list using recursion

Хотя данный исходный вопрос на Stackoverflow более широкий, так как спрашивается помимо прочего как внести данные в список, чтобы продемонстрировать рекурсивную функцию обращения списка, в данной теме будет рассмотрен лишь вопрос, как написать такую рекурсивную функцию обращения списка. Приведенный в качестве примера вопрос будет оставлен без критического анализа.

Ниже показана демонстрационная программа, в которой показано, как можно такую рекурсивную функцию реализовать на C.

 
 #include <stdio.h> 
 #include <stdlib.h> 
  
 struct node 
 { 
     int i; 
     struct node *link; 
 }; 
  
 int push_front( struct node **head, int i ) 
 { 
     node *current = malloc( sizeof( struct node ) ); 
     int success = current != NULL; 
      
     if ( success ) 
     { 
         current->i = i; 
         current->link = *head; 
         *head = current; 
     } 
      
     return success; 
 } 
  
 void print( struct node **head ) 
 { 
     for ( struct node *current = *head; current; current = current->link ) 
     { 
         printf( "%d ", current->i ); 
     }         
 } 
  
 void reverse( struct node **head ) 
 { 
     if ( *head && ( *head )->link ) 
     { 
         struct node *current = *head; 
         *head = ( *head )->link; 
         reverse( head ); 
         current->link->link = current; 
         current->link = NULL; 
     }         
 } 
  
 int main( void )  
 { 
     struct node *head = NULL; 
     const int N = 10; 
      
     for ( int i = 0; i < N; i++ ) push_front( &head, i ); 
      
     print( &head ); 
     putchar( '\n' ); 
      
     reverse( &head ); 
      
     print( &head ); 
     putchar( '\n' ); 
 }     
 

Вывод программы на консоль:

 
 9 8 7 6 5 4 3 2 1 0  
 0 1 2 3 4 5 6 7 8 9