Given a linked list, print reverse of it using a recursive function. For example, if the given linked list is 1->2->3->4, then output should be 4->3->2->1.

Note that the question is only about printing the reverse. To reverse the list itself see this

Difficulty Level:
Rookie

C Algorithm - Write a recursive function to print reverse of a Linked List

Algorithm

printReverse(head)
  1. call print reverse for hed->next
  2. print head->data
[ad type=”banner”]

C Programming:

[pastacode lang=”c” manual=”%2F%2F%20C%20program%20to%20print%20reverse%20of%20a%20linked%20list%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node*%20next%3B%0A%7D%3B%0A%20%20%0A%2F*%20Function%20to%20reverse%20the%20linked%20list%20*%2F%0Avoid%20printReverse(struct%20node*%20head)%0A%7B%0A%20%20%20%20%2F%2F%20Base%20case%20%20%0A%20%20%20%20if%20(head%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20return%3B%0A%20%0A%20%20%20%20%2F%2F%20print%20the%20list%20after%20head%20node%0A%20%20%20%20printReverse(head-%3Enext)%3B%0A%20%0A%20%20%20%20%2F%2F%20After%20everything%20else%20is%20printed%2C%20print%20head%0A%20%20%20%20printf(%22%25d%20%20%22%2C%20head-%3Edata)%3B%0A%7D%0A%20%20%0A%2F*UTILITY%20FUNCTIONS*%2F%0A%2F*%20Push%20a%20node%20to%20linked%20list.%20Note%20that%20this%20function%0A%20%20changes%20the%20head%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20char%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%20%20%20%0A%20%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20pochar%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%20%0A%20%20%0A%2F*%20Drier%20program%20to%20test%20above%20function*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Let%20us%20create%20linked%20list%201-%3E2-%3E3-%3E4%0A%20%20%20%20struct%20node*%20head%20%3D%20NULL%3B%20%20%20%20%0A%20%20%20%20push(%26head%2C%204)%3B%0A%20%20%20%20push(%26head%2C%203)%3B%0A%20%20%20%20push(%26head%2C%202)%3B%0A%20%20%20%20push(%26head%2C%201)%3B%0A%20%20%20%0A%20%20%20%20printReverse(head)%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]

Output:

4 3 2 1

Time Complexity: O(n)

[ad type=”banner”]