package linkedlist;


public class InsertSortLinkedList {


    /*
     * Given head pointer of a linked list, sort the linked list (in ascending order) using insertion sort
     * and return new head pointer of the sorted linked list.
     * Eg: Input:  29 -> 23 -> 82 -> 11,
     *     Output: 11 -> 23 -> 29 -> 82.
     * */

    /*
     * Insertion Sort is very simple. Two linked lists will be maintained:
     * Original list (given to us as input).
     * Sorted list (initially empty).
     *
     * Algorithm:
     * While Original list is not empty:
     * Remove an element 'a' from the Original list.
     * Insert 'a' at correct sorted position in the Sorted list.
     * In order to insert a node in Sorted linked list we may need to scan the whole sorted list depending upon the node being inserted.
     * */

    public static LinkedList.Node sortedInsert(LinkedList.Node head,
                                               LinkedList.Node node) {

        if (node == null) {
            return head;
        }

        if (head == null || node.data <= head.data) {
            node.next = head;
            return node;
        }

        LinkedList.Node curr = head;
        while (curr.next != null && (curr.next.data < node.data)) {
            curr = curr.next;
        }

        node.next = curr.next;
        curr.next = node;

        return head;
    }


    public static LinkedList.Node insertionSort(LinkedList.Node head) {

        LinkedList.Node sorted = null;
        LinkedList.Node curr = head;

        while (curr != null) {
            LinkedList.Node temp = curr.next;
            sorted = sortedInsert(sorted, curr);
            curr = temp;
        }

        return sorted;
    }


    private static class LinkedList {

        private Node head;
        private Node tail;

        public LinkedList(Integer value) {
            head = new Node(value);
            tail = head;
        }

        public void add(Node node) {
            tail.setNext(node);
            tail = node;
        }

        public Node head() {
            return head;
        }

        public void printNode(Node node) {
            while (node != null) {
                System.out.print(node.data + " ");
                node = node.next;
            }
        }

        public static class Node {
            private Node next;
            private Integer data;

            public Node(Integer data) {
                this.data = data;
            }

            public Node next() {
                return next;
            }

            public void setNext(Node next) {
                this.next = next;
            }

            public Integer data() {
                return data;
            }

            public void setData(Integer data) {
                this.data = data;
            }
        }
    }


    public static void main(String[] args) {

        LinkedList linkedList = new LinkedList(3);
        linkedList.add(new LinkedList.Node(1));
        linkedList.add(new LinkedList.Node(5));
        linkedList.add(new LinkedList.Node(4));
        linkedList.add(new LinkedList.Node(9));
        linkedList.add(new LinkedList.Node(0));

        System.out.println("Original: ");
        linkedList.printNode(linkedList.head);
        linkedList.head = insertionSort(linkedList.head);

        System.out.println("Sorted: ");
        linkedList.printNode(linkedList.head);
    }
}