Redirecting to
NADOS

Fold A Linked List

  Prev   Next

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 fold function. The function is expected to place last element after 1st element, 2nd last element after 2nd element and so on. For more insight check the example

Example 1
1->2->3->4->5
will fold as
1->5->2->4->3

Example 2
1->2->3->4->5->6
1->6->2->5->3->4
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 -> Recursion space, O(n)
Sample Input 
5
1 2 3 4 5
10
20
Sample Output 
1 2 3 4 5 
1 5 2 4 3 
10 1 5 2 4 3 20


  • Editorial

    The problem deals with rearranging the linked list or folding the list. Suppose we have a list of length n indexed from 0 to (n-1) then, our output list should be of the format: 0th Index -> (n-1)th Index -> 1st Index -> (n-2)th Index -> 2nd Index -> (n-3)th Index ... and so on.

    Say for example a list 1->2->3->4->5will fold as1->5->2->4->3 and a list with even length 1->2->3->4->5->6 will fold as 1->6->2->5->3->4.

    To solve this problem, we can make use of recursion. Here we will keep a global pointer that will point to the tail of our output resultant list. Now during back - recursion (or function return from recursion stack) we will do the following operations:

    1. (index+1)> size/2

    This is the case when we need to fold the list. This case implies that the node is at the right half of the list and hence needs to be rearranged. So for that, we will add it to the tail of the output list and update its next pointer.

    2. (index+1) == size/2

    This is the case for the last element in the output list so for that we simply need to add this element and set its next pointer to null.

    3. (index+1)< size/2

    This is the case when our element was on the left half, these are the elements that are already taken care of so we need not consider them and return.

    Below is the implementation in Java: 

    private void foldHelper(Node right, int floor) {
                                    if (right == null) {
                                    return;
                                    }
                                    foldHelper(right.next, floor + 1); 
                                    if (floor > size / 2) {
                                    Node temp = fleft.next;
                                    fleft.next = right;
                                    right.next = temp; 
                                    fleft = temp;
                                    } else if(floor == size / 2){
                                    tail = right;
                                    tail.next = null;
                                    }
                                } 
                                Node fleft; 
                                public void fold() {
                                    fleft = head;
                                    foldHelper(head, 0);
                                }

    java false

    Time Complexity: O(n)

    The time complexity for the function is linear as we are traversing on every node.

    Space Complexity: O(n)

    The space complexity for the function is linear as we have n function calls hence we have consumed a linear space in the recursion stack.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name