[ADSx] - LinkedListFun

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack;

class SLLNode<E> {
    protected E element;
    protected SLLNode<E> succ;

    public SLLNode(E elem, SLLNode<E> succ) {
        this.element = elem;
        this.succ = succ;
    }

    @Override
    public String toString() {
        //    return "(" + element.toString() + ")";
        return element.toString();
    }
}

class SLL<E> {
    private SLLNode<E> first;

    public SLL() {
        // Construct an empty SLL
        this.first = null;
    }

    public void deleteList() {
        first = null;
    }

    public int length() {
        int ret;
        if (first != null) {
            SLLNode<E> tmp = first;
            ret = 1;
            while (tmp.succ != null) {
                tmp = tmp.succ;
                ret++;
            }
            return ret;
        } else
            return 0;

    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        if (first != null) {
            SLLNode<E> tmp = first;
            sb.append(tmp).append(" ");
            while (tmp.succ != null) {
                tmp = tmp.succ;
                sb.append(tmp).append(" ");
            }
        } else
            sb = new StringBuilder("Prazna lista!!!");
        return sb.toString();
    }

    public void insertFirst(E o) {
        SLLNode<E> ins = new SLLNode<E>(o, first);
        first = ins;
    }

    public void insertAfter(E o, SLLNode<E> node) {
        if (node != null) {
            SLLNode<E> ins = new SLLNode<E>(o, node.succ);
            node.succ = ins;
        } else {
            System.out.println("Dadenot jazol e null");
        }
    }

    public void insertBefore(E o, SLLNode<E> before) {

        if (first != null) {
            SLLNode<E> tmp = first;
            if (first == before) {
                this.insertFirst(o);
                return;
            }
            //ako first!=before
            while (tmp.succ != before)
                tmp = tmp.succ;
            if (tmp.succ == before) {
                SLLNode<E> ins = new SLLNode<E>(o, before);
                tmp.succ = ins;
            } else {
                System.out.println("Elementot ne postoi vo listata");
            }
        } else {
            System.out.println("Listata e prazna");
        }
    }

    public void insertLast(E o) {
        if (first != null) {
            SLLNode<E> tmp = first;
            while (tmp.succ != null)
                tmp = tmp.succ;
            SLLNode<E> ins = new SLLNode<E>(o, null);
            tmp.succ = ins;
        } else {
            insertFirst(o);
        }
    }

    public E deleteFirst() {
        if (first != null) {
            SLLNode<E> tmp = first;
            first = first.succ;
            return tmp.element;
        } else {
            System.out.println("Listata e prazna");
            return null;
        }
    }

    public E delete(SLLNode<E> node) {
        if (first != null) {
            SLLNode<E> tmp = first;
            if (first == node) {
                return this.deleteFirst();
            }
            while (tmp.succ != node && tmp.succ.succ != null)
                tmp = tmp.succ;
            if (tmp.succ == node) {
                tmp.succ = tmp.succ.succ;
                return node.element;
            } else {
                System.out.println("Elementot ne postoi vo listata");
                return null;
            }
        } else {
            System.out.println("Listata e prazna");
            return null;
        }

    }

    public SLLNode<E> getFirst() {
        return first;
    }

    public void setFirst(SLLNode<E> first) {
        this.first = first;
    }

    public SLLNode<E> find(E o) {
        if (first != null) {
            SLLNode<E> tmp = first;
            while (tmp.element != o && tmp.succ != null)
                tmp = tmp.succ;
            if (tmp.element == o) {
                return tmp;
            } else {
                System.out.println("Elementot ne postoi vo listata");
            }
        } else {
            System.out.println("Listata e prazna");
        }
        return first;
    }

    public Iterator<E> iterator() {
        // Return an iterator that visits all elements of this list, in left-to-right order.
        return new LRIterator<E>();
    }

    // //////////Inner class ////////////

    private class LRIterator<E> implements Iterator<E> {

        private SLLNode<E> place, curr;

        private LRIterator() {
            place = (SLLNode<E>) first;
            curr = null;
        }

        public boolean hasNext() {
            return (place != null);
        }

        public E next() {
            if (place == null)
                throw new NoSuchElementException();
            E nextElem = place.element;
            curr = place;
            place = place.succ;
            return nextElem;
        }

        public void remove() {
            //Not implemented
        }
    }

    public <E extends Number> SLLNode<E> insertFirst(E element, SLLNode<E> first) {
        SLLNode<E> insert = new SLLNode<E>(element, first);
        return insert;
    }

    public <E extends Number> void insertBefore(E element, SLLNode<E> first, SLLNode<E> before) {
        if (first != null) {
            SLLNode<E> tmp = first;
            if (first == before) {
                insertFirst(element, first);
                return;
            }
            //ako first!=before
            while (tmp.succ != before)
                tmp = tmp.succ;

            if (tmp.succ == before) {
                SLLNode<E> ins = new SLLNode<E>(element, before);
                tmp.succ = ins;
            } else {
                System.out.println("Elementot ne postoi vo listata");
            }
        } else {
            System.out.println("Listata e prazna");
        }
    }

    public void mirror() {
        if (first != null) {
            SLLNode<E> tmp = first;
            SLLNode<E> newsucc = null;
            SLLNode<E> next;

            while (tmp != null) {
                next = tmp.succ;
                tmp.succ = newsucc;
                newsucc = tmp;
                tmp = next;
            }
            first = newsucc;
        }

    }

    public void merge(SLL<E> in) {
        if (first != null) {
            SLLNode<E> tmp = first;
            while (tmp.succ != null)
                tmp = tmp.succ;
            tmp.succ = in.getFirst();
        } else {
            first = in.getFirst();
        }
    }

    public void deleteDuplicates() {
        /**
         * https://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list/
         */

        if (first != null) {
            SLLNode<E> i = null, j = null;
            i = first;

            /* Pick elements one by one */
            while (i != null && i.succ != null) {
                j = i;

                /* Compare the picked element with rest of the elements */
                while (j.succ != null) {

                    /* If duplicate then delete it */
                    if (i.element == j.succ.element) {

                        /* sequence of steps is important here */
                        j.succ = j.succ.succ;

                        System.gc();
                    } else /* This is tricky */ {
                        j = j.succ;
                    }
                }
                i = i.succ;
            }
        } else System.out.println("The linked list is empty.");
    }

    public void print_recursive_reverse(SLLNode<E> node) {
        if (node == null) return;
        print_recursive_reverse(node.succ);
        if (node.succ == null) System.out.print(node.element);
        else System.out.print("->" + node.element);
    }

    public SLLNode<E> reverse(SLL<E> list) {
        SLLNode<E> temp = list.getFirst();

        int length = list.length();
        for (int i = 0; i < length; i++) {
            list.insertFirst(temp.succ.element);
            list.getFirst().succ = temp.succ.succ;
            list.insertLast(temp.element);
            temp = temp.succ;
        }
        temp = list.getFirst();
        return temp;
    }

    public void pairwiseSwapData() {
        SLLNode<E> temp = this.getFirst();
        E temp2;
        while (temp != null && temp.succ != null) {
            temp2 = temp.succ.element;
            temp.succ.element = temp.element;
            temp.element = temp2;

            temp = temp.succ.succ;
        }
    }

    public SLLNode<E> reverse(SLLNode<E> node) {
        /**
         * https://www.geeksforgeeks.org/reverse-a-linked-list/
         * */
        SLLNode<E> current = node;
        SLLNode<E> following = null;
        SLLNode<E> previous = null;

        while (current != null) {
            following = current.succ;
            current.succ = previous;
            previous = current;
            current = following;
        }

        node = previous;
        return node;
    }

    public SLLNode<E> reverseGroupKRecursion(SLLNode<E> node, int size) {
        /**
         * https://www.geeksforgeeks.org/reverse-a-list-in-groups-of-given-size/
         * */
        SLLNode<E> current = node;
        SLLNode<E> following = null;
        SLLNode<E> previous = null;

        int count = 0;

        while (count < size && current != null) {
            following = current.succ;
            current.succ = previous;
            previous = current;
            current = following;
            count++;
        }

        if (following != null) node.succ = reverseGroupKRecursion(following, size);

        return previous;
    }

    public SLLNode<E> reverseGroupKStack(SLLNode<E> node, int size) {
        /**
         * https://www.geeksforgeeks.org/reverse-linked-list-groups-given-size-set-2/
         * */
        Stack<SLLNode<E>> stack = new Stack<>();

        SLLNode<E> current = node;
        SLLNode<E> following = null;
        SLLNode<E> previous = null;

        while (current != null) {

            int count = 0;

            while (current != null && count < size) {
                stack.push(current);
                current = current.succ;
                count++;
            }

            while (!stack.isEmpty()) {
                if (previous == null) {
                    previous = stack.pop();
                    node = previous;
                } else {
                    previous.succ = stack.pop();
                    previous = previous.succ;
                }
            }
        }

        previous.succ = null;

        return node;
    }

    public SLLNode<E> reverseBetween(SLLNode<E> node, int start, int end) {
        if (start == end) return node;

        SLLNode<E> nodeStart = null;
        SLLNode<E> nodeEnd = null;
        SLLNode<E> nodeStart_Previous = null;
        SLLNode<E> nodeEnd_Following = null;

        int count = 1;
        SLLNode<E> current = node;

        while (count <= end && current != null) {
            if (count < start) {
                nodeStart_Previous = current;
            }

            if (count == start) {
                nodeStart = current;
            }

            if (count == end) {
                nodeEnd = current;
                nodeEnd_Following = current.succ;
            }

            current = current.succ;
            count++;
        }
        nodeEnd.succ = null;

        nodeEnd = reverse(nodeStart);

        if (nodeStart_Previous != null) {
            nodeStart_Previous.succ = nodeEnd;
        } else {
            node = nodeEnd;
        }

        nodeStart.succ = nodeEnd_Following;
        return node;
    }

    public <E extends Number> SLLNode<E> insertArithmeticalMeans(SLLNode<E> node) {

        SLLNode<E> previous = node;
        SLLNode<E> current = node.succ;
        SLLNode<E> following = node.succ.succ;

        while (current != null) {

            Integer a = previous.element.intValue();
            Integer b = current.element.intValue();

            Integer mean = (a + b) / 2;

            insertBefore((E) mean, node, current);

            System.out.print(previous + " " + current + "\n");

            previous = current;
            current = current.succ;
        }
        return node;
    }

}

class DetectAndRemoveLoop {
    static Node head;

    /**
     * https://www.geeksforgeeks.org/detect-and-remove-loop-in-a-linked-list/
     * */

    static class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    // Function that detects loop in the list
    int detectAndRemoveLoop(Node node) {
        Node slow = node, fast = node;
        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            // If slow and fast meet at same point then loop is present
            if (slow == fast) {
                removeLoop(slow, node);
                return 1;
            }
        }
        return 0;
    }

    // Function to remove loop
    void removeLoop(Node loop, Node curr) {
        Node ptr1 = null, ptr2 = null;

        /* Set a pointer to the beging of the Linked List and
         move it one by one to find the first node which is
         part of the Linked List */
        ptr1 = curr;
        while (1 == 1) {

            /* Now start a pointer from loop_node and check if it ever
             reaches ptr2 */
            ptr2 = loop;
            while (ptr2.next != loop && ptr2.next != ptr1) {
                ptr2 = ptr2.next;
            }

            /* If ptr2 reahced ptr1 then there is a loop. So break the
             loop */
            if (ptr2.next == ptr1) {
                break;
            }

            /* If ptr2 did't reach ptr1 then try the next node after ptr1 */
            ptr1 = ptr1.next;
        }

        /* After the end of loop ptr2 is the last node of the loop. So
         make next of ptr2 as NULL */
        ptr2.next = null;
    }

    // Function to print the linked list
    void printList(Node node) {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }

    // Driver program to test above functions
    public static void main(String[] args) {
        DetectAndRemoveLoop list = new DetectAndRemoveLoop();
        list.head = new Node(50);
        list.head.next = new Node(20);
        list.head.next.next = new Node(15);
        list.head.next.next.next = new Node(4);
        list.head.next.next.next.next = new Node(10);

        // Creating a loop for testing
        head.next.next.next.next.next = head.next.next;
        list.detectAndRemoveLoop(head);
        System.out.println("Linked List after removing loop : ");
        list.printList(head);
    }
}

class FlattenLinkedLists {
    /**
     * https://www.geeksforgeeks.org/flattening-a-linked-list/
     * Requires a node with succ & down, generics can't offer the same
     * thus a new result list must be created which wastes memory
     */

    public static void deleteDuplicates(SLL<Integer> list) {
        SLLNode<Integer> i = list.getFirst();
        SLLNode<Integer> j;
        while (i != null) {
            j = i;
            while (j.succ != null) {

                if (i.element.equals(j.succ.element)) {
                    j.succ = j.succ.succ;
                } else {
                    j = j.succ;
                }
            }
            i = i.succ;
        }
    }

    public static void main(String args[]) {
        SLL<SLL<Integer>> list = new SLL<>();
        for (int i = 0; i < 5; i++) {
            SLL<Integer> temp = new SLL<>();
            for (int j = 0; j < 5; j++) {
                temp.insertFirst(j + 1);
            }
            list.insertFirst(temp);
        }

        SLL<Integer> result = new SLL<>();
        SLLNode<SLL<Integer>> node = list.getFirst();
        while (node != null) {
            SLLNode<Integer> subnode = node.element.getFirst();
            while (subnode != null) {
                result.insertFirst(subnode.element.intValue());
                subnode = subnode.succ;
            }
            node = node.succ;
        }

        deleteDuplicates(result);
        System.out.println(result);
    }
}

class ReverseAlternateK_Nodes {

    public static void reverseBetween(SLL<Integer> list, SLLNode<Integer> start, SLLNode<Integer> end) {
        SLLNode<Integer> node = start;

        while (node != end) {
            SLLNode<Integer> toDelete = node;
            list.insertAfter(node.element, end);
            node = node.succ;
            list.delete(toDelete);
        }

    }

    public static void printAlternateK_Nodes(SLL<Integer> list, Integer K) {
        SLLNode<Integer> node = list.getFirst();

        Boolean alternate = true;
        Integer count = K;

        SLLNode<Integer> start = node;
        SLLNode<Integer> end = node;
        while (node != null) {

            if (count == 1) {
                end = node;
                SLLNode<Integer> nextStart = node.succ;

                if (alternate) {
                    reverseBetween(list, start, end);
                }

                if (nextStart == null) break;

                start = nextStart;
                node = start;

                count = K;
                alternate = !alternate;
            }

            count--;

            if (node.succ == null) {
                break;
            }

            node = node.succ;
        }
        reverseBetween(list, start, node);
    }

    public static void main(String args[]) {
        SLL<Integer> list = new SLL<>();
        for (int i = 0; i < 12; i++) {
            list.insertLast(i + 1);
        }

        SLLNode<Integer> start = list.find(1);
        SLLNode<Integer> end = list.find(12);

        System.out.println(list);
        reverseBetween(list, start, end);
        System.out.println(list);
    }
}

class ReverseWordInSentence {
    public static void printWords(SLL<Character> list) {
        SLLNode<Character> current = list.getFirst();

        while (current != null) {

            System.out.print(current.element);

            if (current.succ == null) break;

            if (current.succ.element == ' ') {
                current = current.succ.succ;
                System.out.print("\n");
            } else {
                current = current.succ;
            }
        }
        System.out.print("\n");
    }

    public static void reverseWord(SLLNode<Character> start, SLLNode<Character> end, SLL<Character> list) {
        SLLNode<Character> afterEnd = end.succ;

        while (start != end.succ) {
            list.insertBefore(start.element, afterEnd); // This shifts end.succ
            afterEnd = end.succ; // so we update afterEnd
            SLLNode<Character> toRemove = start;
            start = start.succ;
            list.delete(toRemove);
        }
    }

    public static void reverseWords(SLL<Character> list) {
        SLLNode<Character> current = list.getFirst();

        SLLNode<Character> start = current;
        SLLNode<Character> end;

        while (current != null) {

            if (current.succ == null) {
                end = current;
                reverseWord(start, end, list);
                break;
            }

            if (current.succ.element == ' ') {
                end = current;
                SLLNode<Character> nextStart = current.succ.succ;

                reverseWord(start, end, list);

                start = nextStart;
                current = start;
            } else {
                current = current.succ;
            }
        }
    }

    public static void main(String[] args) {
        String s = "123 45 67 890";

        SLL<Character> list = new SLL<>();
        for (int i = 0; i < s.length(); i++) {
            list.insertLast(s.charAt(i));
        }


        System.out.println(list);

        reverseWords(list);

        System.out.println();
        System.out.printf("Original: 123 45 67 890\n");
        System.out.printf("Expected: 321 54 76 098\n");
        System.out.printf("Result  : %s\n", list);


    }
}

public class LinkedListFun {

    public static void main(String args[]) {
        SLL<Integer> list = new SLL<>();
        for (int i = 0; i < 10; i++) {
            list.insertFirst(i);
        }

        System.out.println(list);
        list.setFirst(list.reverse(list.getFirst()));
        System.out.println(list);
    }
}

/**
 * Првата беше дадени влезови мерења на PM10 честички од тип „Центар 100“ итн и да се најде за некоја општина просечен број на честички,
 * втората беше да се провери бинарно дрво дали е комплетно,
 * третата беше дадено поле mxn со пречки и робот шо се движи по рабовите на полињата (зафаќа 4 полиња наеднаш и не смее да зафаќа поле со пречка) и да се најде најкраток пат од една до друга позиција 3
 */


class Node {
    Integer data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }

    Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }

    @Override
    public String toString() {
        return String.format("(%d)", data);
    }
}

class mySLL {

    public static void main(String args[]) {
        mySLL one = new mySLL();
        mySLL two = new mySLL();

        one.insertFirst(9);
        one.insertFirst(9);
        one.insertFirst(9);

        two.insertFirst(8);
        two.insertFirst(1);

        mySLL ans = one.add(two);

        ans.printList();

    }

    Node first = null;

    void insertFirst(int data) {
        if (first == null) {
            first = new Node(data);
            return;
        }
        Node insert = new Node(data, first);
        first = insert;
    }

    void insertBefore(int data, Node node) {
        if (first == null) {
            insertFirst(data);
            return;
        }

        if (node == null) {
            return;
        }

        if (first == node) {
            insertFirst(data);
            return;
        }

        Node previous = first;
        Node current = first.next;
        while (current != node) {
            previous = current;
            current = current.next;
        }

        Node insert = new Node(data, current);
        previous.next = insert;

    }

    void insertAfter(int data, Node node) {
        if (first == null) {
            insertFirst(data);
            return;
        }

        if (node == null) {
            return;
        }

        Node insert = new Node(data, node.next);
        node.next = insert;

    }

    int length() {
        if (first == null) return 0;
        Node current = first;
        int length = 0;
        while (current != null) {
            length++;
            current = current.next;
        }
        return length;
    }

    void mergeAnotherAlternatively(mySLL that) {
        Node one = first;
        Node two = that.first;

        while (one != null) {

            if (one.next == null) return;

            this.insertAfter(two.data, one);

            one = one.next.next;
            two = two.next;
        }

    }

    int lengthOfLongestSublist(Node node) {
        /**
         * https://www.geeksforgeeks.org/longest-increasing-sublist-linked-list/
         * */

        if (node == null) return 0;
        Node current = node;
        Node following = node.next;

        int maxLength = Integer.MIN_VALUE;
        int length = 0;

        while (current.next != null) {

            if (current.data <= following.data) {
                length++;
            } else {
                length = 0;
            }

            maxLength = Math.max(maxLength, length);

            current = current.next;
            following = current.next;
        }

        return maxLength + 1;
    }

    /**
     * https://www.geeksforgeeks.org/sum-of-two-linked-lists/
     */

    mySLL add(mySLL that) {
        int lenOne = this.length();
        int lenTwo = that.length();
        int diff = 0;

        Node bigger, smaller;

        // temp1 should point to the longer linkedlist
        if (lenTwo > lenOne) {
            bigger = that.first;
            smaller = this.first;
            diff = Math.abs(lenTwo - lenOne);
        } else {
            smaller = that.first;
            bigger = this.first;
            diff = Math.abs(lenTwo - lenOne);
        }

        Node first = bigger;

        // increment temp1 till temp1 and temp2 have same lengths to end of list
        while (diff > 0) {
            bigger = bigger.next;
            diff--;
        }

        mySLL answer = new mySLL();

        int carry = addRecursively(bigger, smaller, answer);

        // if any carry add that to the remaining linkedlist of temp1
        if (carry != 0) {
            int c = addCarry(first, bigger, answer);
            if (c == 1)    // extra carry after final addition - push that as well
                answer.insertFirst(1);
        }

        return answer;
    }

    // add equal lengths of both linked lists recursively - returns carry
    int addRecursively(Node bigger, Node smaller, mySLL answer) {
        if (bigger == null && smaller == null) return 0;

        int sum = bigger.data + smaller.data + addRecursively(bigger.next, smaller.next, answer);

        answer.insertFirst(sum % 10); // push ones digit alone
        return sum / 10; // return carry
    }

    // add carry of addRecursively to remaining linkedlist
    int addCarry(Node first, Node bigger, mySLL answer) {
        if (first == bigger)
            return 1;    // carry from addRecursively added

        int sum = first.data + addCarry(first.next, bigger, answer);
        answer.insertFirst(sum % 10);

        return sum / 10;
    }

    void printList() {
        Node temp = first;
        while (temp != null) {
            System.out.printf("(%d)->", temp.data);
            temp = temp.next;
        }
        System.out.println();
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        Node current = first;
        while (current != null) {
            sb.append(current).append("->");
            current = current.next;
        }
        return sb.toString();
    }
}