递归插入和遍历链表-yiteyi-C++库

我们讨论了不同的方法链表插入 .如何递归创建链接列表？

null

在末尾递归插入： 要使用递归创建链表，请执行以下步骤。下面的步骤是在链表末尾递归插入一个新节点。

C++

                         // Function to insert a new node at the                       
                         // end of linked list using recursion.                       
                         Node* insertEnd(Node* head,                                     int                                     data)                       
                         {                       
                                                 // If linked list is empty, create a                       
                                                 // new node (Assuming newNode() allocates                       
                                                 // a new node with given data)                       
                                                 if                                     (head == NULL)                       
                                                 return                                     newNode(data);                       
           
                                                 // If we have not reached end, keep traversing                       
                                                 // recursively.                       
                                                 else                       
                                                 head->next = insertEnd(head->next, data);                       
                                                 return                                     head;                       
                         }                       

JAVA

                         // Function to insert a new node at the                       
                         // end of linked list using recursion.                       
                         static                                     Node insertEnd(Node head,                                     int                                     data)                       
                         {                       
                                   
                                                 // If linked list is empty, create a                       
                                                 // new node (Assuming newNode() allocates                       
                                                 // a new node with given data)                       
                                                 if                                     (head ==                                     null                                     )                       
                                                 return                                     newNode(data);                       
                                   
                                                 // If we have not reached end, keep traversing                       
                                                 // recursively.                       
                                                 else                       
                                                 head.next = insertEnd(head.next, data);                       
                                   
                                                 return                                     head;                       
                         }                       
           
                         // This code is contributed by rutvik_56                       

Python3

                         # Function to insert a new node at the                       
                         # end of linked list using recursion.                       
                         def                                     insertEnd(head, data):                       
                                   
                                                 # If linked list is empty, create a                       
                                                 # new node (Assuming newNode() allocates                       
                                                 # a new node with given data)                       
                                                 if                                     (head                                     =                                     =                                     None                                     ):                       
                                                 return                                     newNode(data)                       
                                   
                                                 # If we have not reached end,                       
                                                 # keep traversing recursively.                       
                                                 else                                     :                       
                                                 head.                                     next                                     =                                     insertEnd(head.                                     next                                     , data)                       
                                   
                                                 return                                     head                       
           
                         # This code is contributed by divyeshrabadiya07                       

C#

                         // Function to insert a new node at the                       
                         // end of linked list using recursion.                       
                         static                                     Node insertEnd(Node head,                                     int                                     data)                       
                         {                       
                                   
                                                 // If linked list is empty, create a                       
                                                 // new node (Assuming newNode() allocates                       
                                                 // a new node with given data)                       
                                                 if                                     (head ==                                     null                                     )                       
                                                 return                                     newNode(data);                       
                                   
                                                 // If we have not reached end, keep traversing                       
                                                 // recursively.                       
                                                 else                       
                                                 head.next = insertEnd(head.next, data);                       
                                   
                                                 return                                     head;                       
                         }                       
           
                         // This code is contributed by divyesh072019                       

Javascript

                         <script>                       
           
                         // Function to insert a new node at the                       
                         // end of linked list using recursion.                       
                         function                                     insertEnd(head , data)                       
                         {                       
                                   
                                                 // If linked list is empty, create a                       
                                                 // new node (Assuming newNode() allocates                       
                                                 // a new node with given data)                       
                                                 if                                     (head ==                                     null                                     )                       
                                                 {                       
                                                 return                                     newNode(data);                       
                                                 }                       
           
                                                 // If we have not reached end, keep traversing                       
                                                 // recursively.                       
                                                 else                       
                                                 {                       
                                                 head.next = insertEnd(head.next, data);                       
                                                 }                       
                                                 return                                     head;                       
                         }                       
           
                         // This code is contributed by shubhamsingh10                       
           
                         </script>                       

递归遍历列表： 这个想法很简单，我们打印当前节点并重现剩余的列表。

C++

                         void                                     traverse(Node* head)                       
                         {                       
                                                 if                                     (head == NULL)                       
                                                 return                                     ;                       
                                   
                                                 // If head is not NULL, print current node                       
                                                 // and recur for remaining list                       
                                                 cout << head->data <<                                     " "                                     ;                       
           
                                                 traverse(head->next);                       
                         }                       

JAVA

                         static                                     void                                     traverse(Node head)                       
                         {                       
                                                 if                                     (head ==                                     null                                     )                       
                                                 return                                     ;                       
                                   
                                                 // If head is not null, print current node                       
                                                 // and recur for remaining list                       
                                                 System.out.print( head.data +                                     " "                                     );                       
           
                                                 traverse(head.next);                       
                         }                       
           
                         // This code is contributed by SUBHAMSINGH10                       

Python3

                         def                                     traverse(head):                       
                                                 if                                     (head                                     =                                     =                                     None                                     ):                       
                                                 return                       
                                   
                                                 # If head is not None, print current node                       
                                                 # and recur for remaining list                       
                                                 print                                     (head.data, end                                     =                                     " "                                     );                       
                                                 traverse(head.                                     next                                     )                       
                                   
                                                 # This code is contributed by Pratham76                       

C#

                         static                                     void                                     traverse(Node head)                       
                         {                       
                                                 if                                     (head ==                                     null                                     )                       
                                                 return                                     ;                       
                                   
                                                 // If head is not null, print current node                       
                                                 // and recur for remaining list                       
                                                 Console.Write(head.data +                                     " "                                     );                       
           
                                                 traverse(head.next);                       
                         }                       

完整程序： 下面是演示插入和遍历链表的完整程序。

C++

                           // Recursive C++ program to recursively insert                         
                           // a node and recursively print the list.                         
                           #include <bits/stdc++.h>                         
                           using                                        namespace                                        std;                         
                           struct                                        Node {                         
                                                     int                                        data;                         
                                                     Node* next;                         
                           };                         
            
                           // Allocates a new node with given data                         
                           Node *newNode(                                        int                                        data)                         
                           {                         
                                                     Node *new_node =                                        new                                        Node;                         
                                                     new_node->data = data;                         
                                                     new_node->next = NULL;                         
                                                     return                                        new_node;                         
                           }                         
            
                           // Function to insert a new node at the                         
                           // end of linked list using recursion.                         
                           Node* insertEnd(Node* head,                                        int                                        data)                         
                           {                         
                                                     // If linked list is empty, create a                         
                                                     // new node (Assuming newNode() allocates                         
                                                     // a new node with given data)                         
                                                     if                                        (head == NULL)                         
                                                     return                                        newNode(data);                         
            
                                                     // If we have not reached end, keep traversing                         
                                                     // recursively.                         
                                                     else                         
                                                     head->next = insertEnd(head->next, data);                         
                                                     return                                        head;                         
                           }                         
            
                           void                                        traverse(Node* head)                         
                           {                         
                                                     if                                        (head == NULL)                         
                                                     return                                        ;                         
                                      
                                                     // If head is not NULL, print current node                         
                                                     // and recur for remaining list                         
                                                     cout << head->data <<                                        " "                                        ;                         
            
                                                     traverse(head->next);                         
                           }                         
            
                           // Driver code                         
                           int                                        main()                         
                           {                         
                                                     Node* head = NULL;                         
                                                     head = insertEnd(head, 6);                         
                                                     head = insertEnd(head, 8);                         
                                                     head = insertEnd(head, 10);                         
                                                     head = insertEnd(head, 12);                         
                                                     head = insertEnd(head, 14);                         
                                                     traverse(head);                         
                           }                         

JAVA

                           // Recursive Java program to recursively insert                         
                           // a node and recursively print the list.                         
                           class                                        GFG                         
                           {                         
                                      
                           static                                        class                                        Node                         
                           {                         
                                                     int                                        data;                         
                                                     Node next;                         
                           };                         
            
                           // Allocates a new node with given data                         
                           static                                        Node newNode(                                        int                                        data)                         
                           {                         
                                                     Node new_node =                                        new                                        Node();                         
                                                     new_node.data = data;                         
                                                     new_node.next =                                        null                                        ;                         
                                                     return                                        new_node;                         
                           }                         
            
                           // Function to insert a new node at the                         
                           // end of linked list using recursion.                         
                           static                                        Node insertEnd(Node head,                                        int                                        data)                         
                           {                         
                                                     // If linked list is empty, create a                         
                                                     // new node (Assuming newNode() allocates                         
                                                     // a new node with given data)                         
                                                     if                                        (head ==                                        null                                        )                         
                                                     return                                        newNode(data);                         
            
                                                     // If we have not reached end, keep traversing                         
                                                     // recursively.                         
                                                     else                         
                                                     head.next = insertEnd(head.next, data);                         
                                                     return                                        head;                         
                           }                         
            
                           static                                        void                                        traverse(Node head)                         
                           {                         
                                                     if                                        (head ==                                        null                                        )                         
                                                     return                                        ;                         
                                      
                                                     // If head is not null, print current node                         
                                                     // and recur for remaining list                         
                                                     System.out.print( head.data +                                        " "                                        );                         
            
                                                     traverse(head.next);                         
                           }                         
            
                           // Driver code                         
                           public                                        static                                        void                                        main(String args[])                         
                           {                         
                                                     Node head =                                        null                                        ;                         
                                                     head = insertEnd(head,                                        6                                        );                         
                                                     head = insertEnd(head,                                        8                                        );                         
                                                     head = insertEnd(head,                                        10                                        );                         
                                                     head = insertEnd(head,                                        12                                        );                         
                                                     head = insertEnd(head,                                        14                                        );                         
                                                     traverse(head);                         
                           }                         
                           }                         
            
                           // This code is contributed by andrew1234                         

Python3

                           # Recursive Python3 program to                         
                           # recursively insert a node and                         
                           # recursively print the list.                         
                           import                                        math                         
            
                           class                                        Node:                         
                                                     def                                        __init__(                                        self                                        , data):                         
                                                     self                                        .data                                        =                                        data                         
                                                     self                                        .                                        next                                        =                                        None                         
            
                           # Allocates a new node with given data                         
                           def                                        newNode(data):                         
                                                     new_node                                        =                                        Node(data)                         
                                                     new_node.data                                        =                                        data                         
                                                     new_node.                                        next                                        =                                        None                         
                                                     return                                        new_node                         
            
                           # Function to insert a new node at the                         
                           # end of linked list using recursion.                         
                           def                                        insertEnd(head, data):                         
                                      
                                                     # If linked list is empty, create a                         
                                                     # new node (Assuming newNode() allocates                         
                                                     # a new node with given data)                         
                                                     if                                        (head                                        =                                        =                                        None                                        ):                         
                                                     return                                        newNode(data)                         
            
                                                     # If we have not reached end,                         
                                                     # keep traversing recursively.                         
                                                     else                                        :                         
                                                     head.                                        next                                        =                                        insertEnd(head.                                        next                                        , data)                         
                                                     return                                        head                         
            
                           def                                        traverse(head):                         
                                                     if                                        (head                                        =                                        =                                        None                                        ):                         
                                                     return                         
                                      
                                                     # If head is not None, print current node                         
                                                     # and recur for remaining list                         
                                                     print                                        (head.data, end                                        =                                        " "                                        );                         
                                                     traverse(head.                                        next                                        )                         
            
                           # Driver code                         
                           if                                        __name__                                        =                                        =                                        '__main__'                                        :                         
                                                     head                                        =                                        None                         
                                                     head                                        =                                        insertEnd(head,                                        6                                        )                         
                                                     head                                        =                                        insertEnd(head,                                        8                                        )                         
                                                     head                                        =                                        insertEnd(head,                                        10                                        )                         
                                                     head                                        =                                        insertEnd(head,                                        12                                        )                         
                                                     head                                        =                                        insertEnd(head,                                        14                                        )                         
                                                     traverse(head)                         
            
                           # This code is contributed by sapna singh                         

C#

                           // Recursive C# program to recursively insert                         
                           // a node and recursively print the list.                         
                           using                                        System;                         
            
                           class                                        GFG                         
                           {                         
                                      
                           public                                        class                                        Node                         
                           {                         
                                                     public                                        int                                        data;                         
                                                     public                                        Node next;                         
                           };                         
            
                           // Allocates a new node with given data                         
                           static                                        Node newNode(                                        int                                        data)                         
                           {                         
                                                     Node new_node =                                        new                                        Node();                         
                                                     new_node.data = data;                         
                                                     new_node.next =                                        null                                        ;                         
                                                     return                                        new_node;                         
                           }                         
            
                           // Function to insert a new node at the                         
                           // end of linked list using recursion.                         
                           static                                        Node insertEnd(Node head,                                        int                                        data)                         
                           {                         
                                                     // If linked list is empty, create a                         
                                                     // new node (Assuming newNode() allocates                         
                                                     // a new node with given data)                         
                                                     if                                        (head ==                                        null                                        )                         
                                                     return                                        newNode(data);                         
            
                                                     // If we have not reached end, keep traversing                         
                                                     // recursively.                         
                                                     else                         
                                                     head.next = insertEnd(head.next, data);                         
                                                     return                                        head;                         
                           }                         
            
                           static                                        void                                        traverse(Node head)                         
                           {                         
                                                     if                                        (head ==                                        null                                        )                         
                                                     return                                        ;                         
                                      
                                                     // If head is not null, print current node                         
                                                     // and recur for remaining list                         
                                                     Console.Write(head.data +                                        " "                                        );                         
            
                                                     traverse(head.next);                         
                           }                         
            
                           // Driver code                         
                           public                                        static                                        void                                        Main(String []args)                         
                           {                         
                                                     Node head =                                        null                                        ;                         
                                                     head = insertEnd(head, 6);                         
                                                     head = insertEnd(head, 8);                         
                                                     head = insertEnd(head, 10);                         
                                                     head = insertEnd(head, 12);                         
                                                     head = insertEnd(head, 14);                         
                                                     traverse(head);                         
                           }                         
                           }                         
            
                           // This code is contributed by 29AjayKumar                         

Javascript

                           <script>                         
                                                     // Recursive Javascript program to recursively insert                         
                                                     // a node and recursively print the list.                         
                                      
                                                     class Node                         
                                                     {                         
                                                     constructor(data) {                         
                                                     this                                        .next =                                        null                                        ;                         
                                                     this                                        .data = data;                         
                                                     }                         
                                                     }                         
                                      
                                                     // Allocates a new node with given data                         
                                                     function                                        newNode(data)                         
                                                     {                         
                                                     let new_node =                                        new                                        Node(data);                         
                                                     return                                        new_node;                         
                                                     }                         
            
                                                     // Function to insert a new node at the                         
                                                     // end of linked list using recursion.                         
                                                     function                                        insertEnd(head, data)                         
                                                     {                         
                                                     // If linked list is empty, create a                         
                                                     // new node (Assuming newNode() allocates                         
                                                     // a new node with given data)                         
                                                     if                                        (head ==                                        null                                        )                         
                                                     return                                        newNode(data);                         
            
                                                     // If we have not reached end, keep traversing                         
                                                     // recursively.                         
                                                     else                         
                                                     head.next = insertEnd(head.next, data);                         
                                                     return                                        head;                         
                                                     }                         
            
                                                     function                                        traverse(head)                         
                                                     {                         
                                                     if                                        (head ==                                        null                                        )                         
                                                     return                                        ;                         
            
                                                     // If head is not null, print current node                         
                                                     // and recur for remaining list                         
                                                     document.write(head.data +                                        " "                                        );                         
            
                                                     traverse(head.next);                         
                                                     }                         
                                      
                                                     let head =                                        null                                        ;                         
                                                     head = insertEnd(head, 6);                         
                                                     head = insertEnd(head, 8);                         
                                                     head = insertEnd(head, 10);                         
                                                     head = insertEnd(head, 12);                         
                                                     head = insertEnd(head, 14);                         
                                                     traverse(head);                         
            
                           // This code is contributed by mukesh07.                         
                           </script>                         

输出：

6 8 10 12 14

本文由 阿米特·库马尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章