Given a linked list, print alternate nodes of this linked list.
Examples :
Input : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 Output : 1 -> 3 -> 5 -> 7 -> 9 Input : 10 -> 9 Output : 10
Recursive Approach :
- Initialize a static variable(say flag)
- If flag is odd print the node
- increase head and flag by 1, and recurse for next nodes.
Implementation:
C++
// CPP code to print alternate nodes// of a linked list using recursion#include <bits/stdc++.h>using namespace std;// A linked list nodestruct Node { int data; struct Node* next;};// Inserting node at the beginningvoid push(struct Node** head_ref, int new_data){ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;}// Function to print alternate nodes of linked list.// The boolean flag isOdd is used to find if the current// node is even or odd.void printAlternate(struct Node* node, bool isOdd=true){ if (node == NULL) return; if (isOdd == true) cout << node->data << " "; printAlternate(node->next, !isOdd);}// Driver codeint main(){ // Start with the empty list struct Node* head = NULL; // construct below list // 1->2->3->4->5->6->7->8->9->10 push(&head, 10); push(&head, 9); push(&head, 8); push(&head, 7); push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); printAlternate(head); return 0;} |
Java
// Java code to print alternate nodes // of a linked list using recursion class GFG {// A linked list node static class Node { int data; Node next; }; // Inserting node at the beginning static Node push( Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref;} // Function to print alternate nodes of linked list. // The boolean flag isOdd is used to find if the current // node is even or odd. static void printAlternate( Node node, boolean isOdd) { if (node == null) return; if (isOdd == true) System.out.print( node.data + " "); printAlternate(node.next, !isOdd); } // Driver code public static void main(String args[]){ // Start with the empty list Node head = null; // construct below list // 1.2.3.4.5.6.7.8.9.10 head = push(head, 10); head = push(head, 9); head = push(head, 8); head = push(head, 7); head = push(head, 6); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); printAlternate(head,true); }}// This code is contributed by Arnab Kundu |
Python3
# Python3 code to print alternate nodes # of a linked list using recursion # A linked list nodeclass Node: def __init__(self, data): self.data = data self.next = None# Inserting node at the beginning def push( head_ref, new_data): new_node = Node(new_data); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return head_ref; # Function to print alternate nodes of # linked list. The boolean flag isOdd # is used to find if the current node# is even or odd. def printAlternate( node, isOdd): if (node == None): return; if (isOdd == True): print( node.data, end = " "); if (isOdd == True): isOdd = False; else: isOdd = True; printAlternate(node.next, isOdd); # Driver code # Start with the empty list head = None; # construct below list # 1->2->3->4->5->6->7->8->9->10 head = push(head, 10); head = push(head, 9); head = push(head, 8); head = push(head, 7); head = push(head, 6); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); printAlternate(head, True); # This code is contributed by 29AjayKumar |
C#
// C# code to print alternate nodes // of a linked list using recursion using System;class GFG { // A linked list node public class Node { public int data; public Node next; }; // Inserting node at the beginning static Node push( Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref;} // Function to print alternate nodes of linked list. // The boolean flag isOdd is used to find if the current // node is even or odd. static void printAlternate( Node node, bool isOdd) { if (node == null) return; if (isOdd == true) Console.Write( node.data + " "); printAlternate(node.next, !isOdd); } // Driver code public static void Main(String []args){ // Start with the empty list Node head = null; // construct below list // 1.2.3.4.5.6.7.8.9.10 head = push(head, 10); head = push(head, 9); head = push(head, 8); head = push(head, 7); head = push(head, 6); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); printAlternate(head,true); }}// This code has been contributed by 29AjayKumar |
Javascript
<script>// javascript code to print alternate nodes // of a linked list using recursion // A linked list nodeclass Node { constructor(val) { this.data = val; this.next = null; }} // Inserting node at the beginning function push(head_ref , new_data) {var new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } // Function to print alternate nodes of linked list. // The boolean flag isOdd is used to find if the current // node is even or odd. function printAlternate(node, isOdd) { if (node == null) return; if (isOdd == true) document.write(node.data + " "); printAlternate(node.next, !isOdd); } // Driver code // Start with the empty listvar head = null; // construct below list // 1.2.3.4.5.6.7.8.9.10 head = push(head, 10); head = push(head, 9); head = push(head, 8); head = push(head, 7); head = push(head, 6); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); printAlternate(head, true);// This code contributed by umadevi9616 </script> |
Output:
1 3 5 7 9
Time complexity: O(N) where N is no of nodes in linked list
Auxiliary space: O(1), If we consider recursive call stack then it would be O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Read More Information here on that Topic: geeksforgeeks.org/print-alternate-nodes-of-a-linked-list-using-recursion/ […]
… [Trackback]
[…] Info on that Topic: geeksforgeeks.org/print-alternate-nodes-of-a-linked-list-using-recursion/ […]