/*
  Date: 2020-12-24
  Author: Leonardo Tamiano

 */

#include <stdio.h>
#include <stdlib.h>

struct nodo{
	int inf;
	struct nodo *prec, *succ;
};
typedef struct nodo nodo;

nodo *add_first(nodo *l, int k);
nodo *add_second(nodo *l, int k);
int count_length(nodo *l);
nodo *Range(nodo *a, int i, int j, int k);

// ---------------------------------
// Funzioni extra
//

nodo *add_first(nodo *l, int k)
{
  nodo *n0 = malloc(sizeof(nodo));
	
  if(!n0) return l;

  n0->inf = k;
  n0->prec = NULL;
  n0->succ = l;
	
  if(l) l->prec = n0;
	
  return n0;
}

nodo *add_second(nodo *l, int k)
{
  if(!l) return l;

  nodo *n1 = malloc(sizeof(nodo));
  if(!n1) return l;

  n1->inf = k;
  n1->prec = l;
  n1->succ = l->succ;
  
  if(l->succ) l->succ->prec = n1;
  l->succ = n1;
  
  return l;
}

int count_length(nodo *l) {
  int len;
  nodo *t;

  for(t = l, len = 0; t; t = t->succ, len++);

  return len;
}

// ---------------------------------
// Funzione richiesta per esame
//

// Tempo: O((j - 1)/k), ovvero il numero di elementi della sequenza
// Memoria: O((j - 1)/k)
nodo *Range(nodo *a, int i, int j, int k) {
  int t;
  nodo *n, *h;
  
  // k = 0
  if(k == 0) return NULL;

  n = add_first(NULL, i);
  h = n;
  t = i;

  while(((k > 0) && (t + k) < j) || ((k < 0) && (t + k) > j)) {
    t = t + k;
    h = add_second(h, t);
    h = h->succ;
  }

  return n;
}