csll

class CSLList<T> {
  class Node {
    // Each Node object has these two fields
    private T element;
    private Node next;

    // Constructor: Creates a Node object with element = e and next = n
    Node(T e, Node n) {
      element = e;
      next = n;
    }

    // This function gets T e as input and sets e as the element of the Node
    public void setElement(T e) {
      element = e;
    }

    // This function returns the element variable of the Node
    public T getElement() {
      return element;
    }

    // This function gets Node n as input and sets the next variable of the current Node object as n.
    public void setNext(Node n) {
      next = n;
    }

    // This function returns the next Node
    public Node getNext() {
      return next;
    }
  }

  // Each object in CSLList has one field tail, which points to the tail Node of CSLList.
  private Node tail;

  /**
    * Constructor: initialises the tail field as null
    */
  public CSLList() {
    tail = null;
  }

  /**
    * @return The element in the first Node of this CSLL. If the list is empty, this method returns null.
    */
  public T getFirst() {
    if (tail == null)
      return null;
    return tail.getNext().getElement();
  }

  /**
    * @return The element in the last Node of this CSLL. If the list is empty, this method returns null.
    */
  public T getLast() {
    if (tail == null)
      return null;
    return tail.getElement();
  }

  /**
    * Adds element e in a new Node to the head of the list.
    *
    * @param e
    *     The element to add.
    */
  public void addFirst(T e) {
    if(tail == null) {
      tail = new Node(e, null);
      tail.setNext(tail);
    }
    else {
      Node node = new Node(e, tail.getNext());
      tail.setNext(node);
    }
  }

  /**
    * Adds element e in a new Node to the tail of the list.
    *
    * @param e
    *     The element to add.
    */
  public void addLast(T e) {
      addFirst(e);
      rotate();
  }

  /**
    * Remove the first Node in the list and return its element.
    *
    * @return The element of the first Node. If the list is empty, this method returns null.
    */
  public T removeFirst() {
    if (tail != null) {
      Node node = tail.getNext();
      if(node == tail) {
        tail = null;
      }
      else {
        tail.setNext(node.getNext());
      }
      return node.getElement();
    }
    return null;
  }

  /**
    * Rotates the list such that the second element in the list will become the first element in the list.
    * Example: rotating the list [1, 2, 3] will become [2, 3, 1].
    */
  public void rotate() {
    if(tail != null) {
      tail = tail.getNext();
    }
  }

  public int size() {
        if (tail == null) {
            return 0;
        }
        int size = 1;
        Node currNode = tail;
        while (currNode.getNext() != tail) {
            size++;
            currNode = currNode.getNext();
        }
        return size;
    }

  /**
    * Merges this list and the other list by alternating elements from the two lists.
    * If one of the lists is longer than the other, the remaining elements are added to the end of the resulting list.
    *
    * @param other
    *     The other list to alternate elements with. Is treated as an empty list if it is null.
    * @return A new list with alternated elements of this list and the other list.
    */
  public CSLList<T> alternate(CSLList<T> other) {
    if(other == null || other.tail == null) {
      return this;
    }
    if (this.tail == null) {
      return other;
    }
    CSLList<T> list = new CSLList<>();
    int thisSize = this.size();
    int otherSize = other.size();
    int min = Math.min(thisSize, otherSize);

    Node nodeA = this.tail.getNext();
    Node nodeB = other.tail.getNext();

    for(int i = 0; i < min; i++) {
      list.addLast(nodeA.getElement());
      list.addLast(nodeB.getElement());
      nodeA = nodeA.getNext();
      nodeB = nodeB.getNext();
    }
    if (min == thisSize) {
      for(int i = 0; i < otherSize-min; i++) {
        list.addLast(nodeB.getElement());
        nodeB = nodeB.getNext();
      }
    }
    else {
      for(int i = 0; i < thisSize-min; i++) {
        list.addLast(nodeA.getElement());
        nodeA = nodeA.getNext();
      }
    }
    return list;
  }

  /**
    * Removes all elements at the odd positions in this list.
    * Note that the head of the list is element number 0, which is an even position.
    */
  public void dropOdd() {
    if (tail == null || tail.getNext() == tail) {
      return;
    }
    int size = size();
    for(int i = 0; i < size; i++) {
      T e = removeFirst();
      if(i % 2 == 0) {
        addLast(e);
      }
    }
  }
}