package linkedlist;


public class SwapNthNodeWithHead {


    /*
     * Given the head of a singly linked list and 'N', swap the head with Nth node. Return the head of the new linked list.
     * Input: 1, 2, 3, 4, 5,
     * Output: Swapping 3rd Node with Head
     * Input: 3, 2, 1, 4, 5,
     * Output: Swapping 5th Node with Head
     *
     * */

    /*
     * Runtime Complexity:
     * Linear, O(n).
     *
     * Memory Complexity:
     * Constant, O(1).
     *
     * To swap the Nth node with head, find the (N-1)th node as we need node '(N-1)->next' to become the new head.
     * Then iterate the list till current points to the Nth node.
     * 'prev' follows current and will be pointing to (N-1)th node.
     *  Return current as the new head of the linked list.
     * */
    public static LinkedList.Node swapNthNode(LinkedList.Node head, int n) {
        LinkedList.Node prev = null;
        LinkedList.Node current = head;

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

        if (n == 1) {
            // No need to swap head with head.
            return head;
        }

        for (int count = 1;
             current != null && count < n;
             ++count) {
            prev = current;
            current = current.next;
        }

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

        // current is pointing to nth node.
        // Let's swap nth node with head.

        prev.next = head;
        LinkedList.Node temp = head.next;
        head.next = current.next;
        current.next = temp;

        return current;
    }

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

        linkedList.printNode(linkedList.head);
        System.out.println();
        linkedList.head = swapNthNode(linkedList.head, 3);
        linkedList.printNode(linkedList.head);
    }
}