StefiIOE

[ADS] Palindrome

Nov 16th, 2020 (edited)
42
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Scanner;
  2.  
  3. class DLLNode<E> {
  4.     protected E element;
  5.     protected DLLNode<E> pred, succ;
  6.  
  7.     public DLLNode(E elem, DLLNode<E> pred, DLLNode<E> succ) {
  8.         this.element = elem;
  9.         this.pred = pred;
  10.         this.succ = succ;
  11.     }
  12.  
  13.     @Override
  14.     public String toString() {
  15.         return "<-" + element.toString() + "->";
  16.     }
  17. }
  18.  
  19. class DLL<E> {
  20.     private DLLNode<E> first, last;
  21.  
  22.     public DLL() {
  23.         // Construct an empty SLL
  24.         this.first = null;
  25.         this.last = null;
  26.     }
  27.  
  28.     public void deleteList() {
  29.         first = null;
  30.         last = null;
  31.     }
  32.  
  33.     public int length() {
  34.         int ret;
  35.         if (first != null) {
  36.             DLLNode<E> tmp = first;
  37.             ret = 1;
  38.             while (tmp.succ != null) {
  39.                 tmp = tmp.succ;
  40.                 ret++;
  41.             }
  42.             return ret;
  43.         } else
  44.             return 0;
  45.  
  46.     }
  47.  
  48.     public void insertFirst(E o) {
  49.         DLLNode<E> ins = new DLLNode<E>(o, null, first);
  50.         if (first == null)
  51.             last = ins;
  52.         else
  53.             first.pred = ins;
  54.         first = ins;
  55.     }
  56.  
  57.     public void insertLast(E o) {
  58.         if (first == null)
  59.             insertFirst(o);
  60.         else {
  61.             DLLNode<E> ins = new DLLNode<E>(o, last, null);
  62.             last.succ = ins;
  63.             last = ins;
  64.         }
  65.     }
  66.  
  67.     public void insertAfter(E o, DLLNode<E> after) {
  68.         if (after == last) {
  69.             insertLast(o);
  70.             return;
  71.         }
  72.         DLLNode<E> ins = new DLLNode<E>(o, after, after.succ);
  73.         after.succ.pred = ins;
  74.         after.succ = ins;
  75.     }
  76.  
  77.     public void insertBefore(E o, DLLNode<E> before) {
  78.         if (before == first) {
  79.             insertFirst(o);
  80.             return;
  81.         }
  82.         DLLNode<E> ins = new DLLNode<E>(o, before.pred, before);
  83.         before.pred.succ = ins;
  84.         before.pred = ins;
  85.     }
  86.  
  87.     public E deleteFirst() {
  88.         if (first != null) {
  89.             DLLNode<E> tmp = first;
  90.             first = first.succ;
  91.             first.pred = null;
  92.             if (first == null)
  93.                 last = null;
  94.             return tmp.element;
  95.         } else
  96.             return null;
  97.     }
  98.  
  99.     public E deleteLast() {
  100.         if (first != null) {
  101.             if (first.succ == null)
  102.                 return deleteFirst();
  103.             else {
  104.                 DLLNode<E> tmp = last;
  105.                 last = last.pred;
  106.                 last.succ = null;
  107.                 return tmp.element;
  108.             }
  109.         }
  110.         // else throw Exception
  111.         return null;
  112.     }
  113.  
  114.     @Override
  115.     public String toString() {
  116.         String ret = new String();
  117.         if (first != null) {
  118.             DLLNode<E> tmp = first;
  119.             ret += tmp + "<->";
  120.             while (tmp.succ != null) {
  121.                 tmp = tmp.succ;
  122.                 ret += tmp + "<->";
  123.             }
  124.         } else
  125.             ret = "Prazna lista!!!";
  126.         return ret;
  127.     }
  128.  
  129.     public DLLNode<E> getFirst() {
  130.         return first;
  131.     }
  132.  
  133.     public DLLNode<E> getLast() {
  134.  
  135.         return last;
  136.     }
  137.    
  138. }
  139.  
  140. public class PalindromeDLL {
  141.    
  142.     public static int isItPalindrome(DLL<Integer> list){
  143.      //   DLL<Integer> result = new DLL<Integer> ();
  144.         DLLNode<Integer> levo = list.getFirst();
  145.         DLLNode<Integer> desno = list.getFirst();
  146.  
  147.         while(desno.succ !=null){
  148.             desno = desno.succ;
  149.         }
  150.         while(levo != desno){
  151.             if(levo.element != desno.element){
  152.                 return -1;
  153.             }
  154.                 levo = levo.succ;
  155.                 desno = desno.pred;
  156.            
  157.         }
  158.         return 1;
  159.     }
  160.    
  161.     public static void main(String[] args) {
  162.         Scanner in = new Scanner(System.in);
  163.         int n = in.nextInt();
  164.         DLL<Integer> list = new DLL<Integer>();
  165.         for (int i = 0; i < n; i++) {
  166.             list.insertLast(in.nextInt());
  167.         }
  168.         in.close();
  169.         System.out.println(isItPalindrome(list));
  170.     }
  171.  
  172. }
  173.  
RAW Paste Data