Question

Write a program to print all the elements of the single linked list in reverse order. The
algorithm should have linear time complexity and constant space complexity

Answer 1

#include <inttypes.h>
#include <malloc.h>
#include <stdio.h>

// linked list implementation
struct list {
  int64_t value;     // value of a node
  struct list *next; // line to the next node of the list
};

struct list *node_create(int64_t value) {          // create a  new node
  struct list *node = malloc(sizeof(struct list)); // allocate a memory in heap
  node->value = value;
  node->next = NULL;
  return node;
}

void list_add_last(struct list **list,
                   int64_t value) { // add a new node to the list
  if (!(*list)) {
    *list = node_create(value);
  } else {
    struct list *node = *list;
    while (node->next) {
      node = node->next;
    }
    node->next = node_create(value);
  }
}

void print(const struct list *list) {
  if (list) {                            // if list is not null
    printf("%" PRId64, list->value); // printing the node value
    if (list->next)
      printf(" -> ");
    print(list->next); // calling function recursively
  }
}

int main() {

  struct list *list = NULL;

  list_add_last(&list, 5);
  list_add_last(&list, 2);
  list_add_last(&list, 3);
  list_add_last(&list, -5);

  print(list); // 5 -> 2 -> 3 -> -5

  return 0;
}