Monday, May 25, 2015

K reverse a linked list with increasing K

Problem
Reverse k elements in the linked list such that k goes on increasing

Example
Eg.        1 - 2 - 3 - 4 - 5 - 6 - 7
output - 1 - 3 - 2 - 6 - 5- 4 - 7

Solution

You can take this problem here. Here we are just increasing k.

   public static ListNode<Integer> reverseSubLinkLists(ListNode<Integer> headerNode) {
        
        ListNode<Integer> nextNode = headerNode.next;
        ListNode<Integer> startNode = null;
        ListNode<Integer> endNode = null;
        
        int k = 2;
        while (nextNode != null) {
            
            startNode = nextNode;
            endNode = nextNode;
            
            for (int i = 1; i < k; i++) {
                endNode = endNode.next;
                if (endNode == null) {
                    break;
                }
            }



            if (endNode != null) {
                // Save the node next to endNode
                nextNode = endNode.next;
                // Unlink the endNode
                endNode.next = null;
                // Reverse the list starting from startNode

                startNode = reverseListIterative(startNode);
                k++;
            } else {
                nextNode = null;
//              // Save the node next to endNode
//              nextNode = endNode.next;
//              // Unlink the endNode
//              endNode.next = null;
                // Reverse the list starting from startNode

                startNode = reverseListIterative(startNode);
            }

            if (headerNode == null) {
                headerNode = startNode;
            } else {
                headerNode.next = startNode;
                ListNode<Integer> temp = startNode;
                while(temp!=null){
                    if(temp.next==null){
                        break;
                    }
                    temp = temp.next;
                }
                headerNode = temp;
            }
        }

        return headerNode;
    }

    public static ListNode<Integer> reverseListIterative(ListNode<Integer> headerNode) {
        ListNode<Integer> prevNode = null;
        ListNode<Integer> currNode = headerNode;
        ListNode<Integer> nextNode = null;

        while (currNode != null) {
            nextNode = currNode.next;
            currNode.next = prevNode;
            prevNode = currNode;
            currNode = nextNode;
        }

        return prevNode;
    }
    

Time complexity - O(n)

0 comments:

Post a Comment