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

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

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

// tempo: O(n) con n lunghezza lista
// memoria: O(1)
nodo *Ruota(nodo *l) {
  nodo *t1, *t2, *t3, *t4;

  // scorri tutta la prima sotto-sequenza non-decrescente
  for(t1 = l, t2 = l->succ;
      t1 && t2 && t1->inf <= t2->inf;
      t1 = t2, t2 = t2->succ);

  if(t2) {
    // scorri tutta la seconda sotto-sequenza non-decrescente
    for(t3 = t2, t4 = t2->succ;
	t3 && t4 && t3->inf <= t4->inf;
	t3 = t4, t4 = t4->succ);

    if(t4) {
      // la lista non è ruotata
      printf("List is NOT rotated!\n");
      return l;
    } else {
      // la lista è ruotata
      printf("List is rotated!\n");

      // invertiamo le due sotto-sequenze non-decrescenti
      t2->prec = NULL;
      t3->succ = l;
      l->prec = t3;
      t1->succ = NULL;

      return t2;
    }
  } else {
    // la lista è ruotata (banalmente)
    printf("List is rotated!\n");
    return l;
  }
}