/*
  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 *Porzione(nodo *a, int i, int j);

// ---------------------------------
// 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(n), con n lunghezza lista
// Memoria: O(j - i), con j - i lunghezza intervallo
nodo *Porzione(nodo *a, int i, int j)
{
  nodo *res, *t;
  int len, h;
  
  len = count_length(a);

  // controlla i casi limite
  if(i > len || i >= j || i < 0) {
    return NULL;
  } else if (j == 0 || j > len) {
    // -- copia da i in poi
    j = len - 1;
  }

  // scorri fino all'i-esimo elemento
  for(h = 0; a && h != i; a = a->succ, h++);

  // copia il primo elemento 
  res = add_first(res, a->inf);
  t = res;
  a = a->succ;
  h++;
  
  // copia i restanti elementi
  while(h < j){
      t = add_second(t, a->inf);
      t = t->succ;
      a = a->succ;
      h++;
  }
  
  return res;
}