K Reverse In Linked List

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a partially written LinkedList class.
2. You are required to complete the body of kReverse function. The function is expected to tweak the list such that all groups of k elements in the list get reversed and linked. If the last set has less than k elements, leave it as it is (don't reverse).
3. Input and Output is managed for you.
Input Format
Input is managed for you
Output Format
Output is managed for you
Question Video
Constraints
1. Time complexity -> O(n)
2. Space complexity -> constant
Sample Input
11
1 2 3 4 5 6 7 8 9 10 11
3
100
200
Sample Output
1 2 3 4 5 6 7 8 9 10 11 
3 2 1 6 5 4 9 8 7 10 11
100 3 2 1 6 5 4 9 8 7 10 11 200


  • Editorial

    The problem deals with reversing an input list in the groups of given size. For example, suppose we have a list 1 ->2 ->3 ->4 ->5 ->6 ->7 ->8 ->9 ->10 ->11 and we have value of k = 3 then our output list should be reversed in group of size 3. Hence the output list will look like:

    3 ->2 ->1 ->6 ->5 ->4 ->9 ->8 ->7 ->10 ->11.

    A vague idea about approaching this problem is to select every group of size k and reverse it until we reach the end, and somehow coagulate the resulting reversed groups to get our result.

    Now to achieve this, we are going to create two lists, one to store the final result and the other to store the temporary reversed groups. Our operations continues until we traverse the entire list or here until the size of the input list is greater than zero.

    Now there can be two cases where our selected group can lie:

    1. this.size() >= k

    This is the case when the remaining list is of length greater than or equal to the group size. This implies that in this case, we need to select a group of size k and reverse it. This can be achieved by selecting every element from the input list (of the selected group) and remove it from the input list and add it to the head of the temporary list, doing this for k times will result in a group of size k reversed and stored in a temporary list, say, we have,

    Input List: 1 -> 2 -> 3 -> 4 -> 5

    then after the above-mentioned operations, we would have:

    Remaining Input List: 4 -> 5

    Temporary List: 3  -> 2 -> 1

    2. this.size() < k

    This is the case when the remaining list is of length is less than the given group size. In this case, we need not reverse the list, rather we have to simply add this list directly to our output list and get our final result.

    All the groups are firstly stored in a temporary list and then are added to the output list where we can have two cases:

    1. Output List is Empty

    This is the case when we have operated on our first group. Here we simply need to have the temporary list as our output list as this group will be the starting elements of our result

    2. Output List is not Empty

    This is the latter case when we already have elements in our output list. In this case, we need to add elements of the temporary list at the end of the output list and later update the tail and size of the output list.

    Lastly, we need to update the output list to the linked list data member.


    Below is the implementation in Java:

    public void kReverse(int k) {
                                        LinkedList prev = null; 
                                        while (this.size > 0) {
                                        LinkedList curr = new LinkedList(); 
                                        if (this.size >= k) {
                                            for (int i = 0; i < k; i++) {
                                            int val = this.getFirst();
                                            this.removeFirst();
                                            curr.addFirst(val);
                                            }
                                        } else {
                                            int sz = this.size;
                                            for (int i = 0; i < sz; i++) {
                                            int val = this.getFirst();
                                            this.removeFirst();
                                            curr.addLast(val);
                                            }
                                        } 
                                        if (prev == null) {
                                            prev = curr;
                                        } else {
                                            prev.tail.next = curr.head;
                                            prev.tail = curr.tail;
                                            prev.size += curr.size;
                                        }
                                        } 
                                        this.head = prev.head;
                                        this.tail = prev.tail;
                                        this.size = prev.size;
                                    }

    java false

    Time Complexity: O(n)

    The time complexity for the function is linear as we are traversing on every node and updating the temporary and output lists which is dependent on the length of the linked list.

    Space Complexity: O(n)

    The space complexity for the function is linear as we have created two lists that store the output lists.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name