package linkedlist;


public class ReversekElements {

    /*
    * Given a singly linked list and an integer 'k', reverse every 'k' elements. If k <= 1, then input list is unchanged.
    * If k >= n (n is the length of linked list), then reverse the whole linked list.
    *
    * Input: 1, 2, 3, 4, 5, 6
    * When k = 3,
    * Output: 3, 2, 1, 6, 5, 4
    *
    * Runtime Complexity:
    * Linear, O(n).
    *
    * Memory Complexity:
    * Constant, O(1).
    *
    *
    * */

    public static LinkedList.Node reverseKNodes(LinkedList.Node head,
                                                int k) {

        // if k is 0 or 1, then list is not changed
        if (k <= 1 || head == null) {
            return head;
        }

        LinkedList.Node reversed = null;
        LinkedList.Node prev_tail = null;

        while (head != null && k > 0) {
            LinkedList.Node current_head = null;
            LinkedList.Node current_tail = head;

            int n = k;
            while (head != null && n > 0) {
                LinkedList.Node temp = head.next;
                head.next = current_head;
                current_head = head;

                head = temp;
                n--;
            }

            if (reversed == null) {
                reversed = current_head;
            }

            if (prev_tail != null) {
                prev_tail.next = current_head;
            }
            prev_tail = current_tail;
        }

        return reversed;
    }

    protected static class LinkedList {

        private Node head;

        public Node head() {
            return head;
        }

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

        /* Inserts a new Node at end of the list. */
        public void push(int new_data) {
            Node newNode = new Node(new_data);
            if (head == null) {
                head = new Node(new_data);
                return;
            }

            newNode.next = null;
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            last.next = newNode;
        }

        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 linkedList1 = new LinkedList();
        linkedList1.push(1);
        linkedList1.push(2);
        linkedList1.push(3);
        linkedList1.push(4);
        linkedList1.push(5);
        linkedList1.push(6);

        System.out.println("List 1: ");
        linkedList1.printNode(linkedList1.head);
        System.out.println();

        LinkedList.Node mergedList = reverseKNodes(linkedList1.head, 3);
        linkedList1.printNode(mergedList);
    }
}