Advertisement
dzocesrce

[APS] Find Pairs

Aug 28th, 2023
402
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.56 KB | None | 0 0
  1. //2020 prv kolokvium - termin 1
  2. import java.util.NoSuchElementException;
  3. import java.util.Scanner;
  4. class SLL<E> {
  5.     private SLLNode<E> first;
  6.  
  7.     public SLL() {
  8.         // Construct an empty SLL
  9.         this.first = null;
  10.     }
  11.  
  12.     public void deleteList() {
  13.         first = null;
  14.     }
  15.  
  16.     public int length() {
  17.         int ret;
  18.         if (first != null) {
  19.             SLLNode<E> tmp = first;
  20.             ret = 1;
  21.             while (tmp.succ != null) {
  22.                 tmp = tmp.succ;
  23.                 ret++;
  24.             }
  25.             return ret;
  26.         } else
  27.             return 0;
  28.  
  29.     }
  30.  
  31.     @Override
  32.     public String toString() {
  33.         String ret = new String();
  34.         if (first != null) {
  35.             SLLNode<E> tmp = first;
  36.             ret += tmp + " ";
  37.             while (tmp.succ != null) {
  38.                 tmp = tmp.succ;
  39.                 ret += tmp + " ";
  40.             }
  41.         } else
  42.             ret = "Prazna lista!!!";
  43.         return ret;
  44.     }
  45.  
  46.     public void insertFirst(E o) {
  47.         SLLNode<E> ins = new SLLNode<E>(o, first);
  48.         first = ins;
  49.     }
  50.  
  51.     public void insertAfter(E o, SLLNode<E> node) {
  52.         if (node != null) {
  53.             SLLNode<E> ins = new SLLNode<E>(o, node.succ);
  54.             node.succ = ins;
  55.         } else {
  56.             System.out.println("Dadenot jazol e null");
  57.         }
  58.     }
  59.  
  60.     public void insertBefore(E o, SLLNode<E> before) {
  61.  
  62.         if (first != null) {
  63.             SLLNode<E> tmp = first;
  64.             if(first==before){
  65.                 this.insertFirst(o);
  66.                 return;
  67.             }
  68.             //ako first!=before
  69.             while (tmp.succ != before)
  70.                 tmp = tmp.succ;
  71.             if (tmp.succ == before) {
  72.                 SLLNode<E> ins = new SLLNode<E>(o, before);
  73.                 tmp.succ = ins;
  74.             } else {
  75.                 System.out.println("Elementot ne postoi vo listata");
  76.             }
  77.         } else {
  78.             System.out.println("Listata e prazna");
  79.         }
  80.     }
  81.  
  82.     public void insertLast(E o) {
  83.         if (first != null) {
  84.             SLLNode<E> tmp = first;
  85.             while (tmp.succ != null)
  86.                 tmp = tmp.succ;
  87.             SLLNode<E> ins = new SLLNode<E>(o, null);
  88.             tmp.succ = ins;
  89.         } else {
  90.             insertFirst(o);
  91.         }
  92.     }
  93.  
  94.     public E deleteFirst() {
  95.         if (first != null) {
  96.             SLLNode<E> tmp = first;
  97.             first = first.succ;
  98.             return tmp.element;
  99.         } else {
  100.             System.out.println("Listata e prazna");
  101.             return null;
  102.         }
  103.     }
  104.  
  105.     public E delete(SLLNode<E> node) {
  106.         if (first != null) {
  107.             SLLNode<E> tmp = first;
  108.             if(first ==node){
  109.                 return this.deleteFirst();
  110.             }
  111.             while (tmp.succ != node && tmp.succ.succ != null)
  112.                 tmp = tmp.succ;
  113.             if (tmp.succ == node) {
  114.                 tmp.succ = tmp.succ.succ;
  115.                 return node.element;
  116.             } else {
  117.                 System.out.println("Elementot ne postoi vo listata");
  118.                 return null;
  119.             }
  120.         } else {
  121.             System.out.println("Listata e prazna");
  122.             return null;
  123.         }
  124.  
  125.     }
  126.  
  127.     public SLLNode<E> getFirst() {
  128.         return first;
  129.     }
  130.  
  131.     public SLLNode<E> find(E o) {
  132.         if (first != null) {
  133.             SLLNode<E> tmp = first;
  134.             while (tmp.element != o && tmp.succ != null)
  135.                 tmp = tmp.succ;
  136.             if (tmp.element == o) {
  137.                 return tmp;
  138.             } else {
  139.                 System.out.println("Elementot ne postoi vo listata");
  140.             }
  141.         } else {
  142.             System.out.println("Listata e prazna");
  143.         }
  144.         return first;
  145.     }
  146.  
  147. }
  148.  
  149. class SLLNode<E> {
  150.     protected E element;
  151.     protected SLLNode<E> succ;
  152.  
  153.     public SLLNode(E elem, SLLNode<E> succ) {
  154.         this.element = elem;
  155.         this.succ = succ;
  156.     }
  157.  
  158.     @Override
  159.     public String toString() {
  160.         return element.toString();
  161.     }
  162. }
  163. public class FindPairs {
  164.     public static void findPairs(SLL<Integer> list) {
  165.         SLLNode<Integer> temp1 = list.getFirst();
  166.         SLLNode<Integer> temp2 = list.getFirst();
  167.         while (temp1.succ != null) {
  168.             temp2 = temp1.succ;
  169.             while (true) {
  170.                 if(temp2==null) break;
  171.                 if (temp1.element % 2 == temp2.element % 2) {
  172.                     if (temp1.element % 2 == 1) {
  173.                         temp1.element -= temp2.element;
  174.                         list.delete(temp2);
  175.                         break;
  176.                     } else {
  177.                         temp1.element += temp2.element;
  178.                         list.delete(temp2);
  179.                         break;
  180.                     }
  181.  
  182.                 }
  183.                 temp2=temp2.succ;
  184.             }
  185.             temp1=temp1.succ;
  186.             if(temp1==null) break;
  187.         }
  188.     }
  189.         public static void main (String[]args){
  190.             SLL<Integer> list = new SLL<Integer>();
  191.             Scanner input = new Scanner(System.in);
  192.             int n = Integer.parseInt(input.nextLine());
  193.             String[] broevi = input.nextLine().split("\\s+");
  194.             for (int i = 0; i < n; i++) {
  195.                 list.insertLast(Integer.parseInt(broevi[i]));
  196.             }
  197.             findPairs(list);
  198.             System.out.println(list);
  199.         }
  200.     }
  201. /*
  202. TestCase1
  203. 8
  204. 1 2 3 4 5 6 7 8
  205. -2 6 -2 14
  206. TestCase2
  207. 10
  208. 7 12 24 2 6 32 11 44 8 10
  209. -4 36 8 76 18
  210.  */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement