Reverse A Linked List (data Iterative)

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. Here is a list of existing functions:
2.1 addLast - adds a new element with given value to the end of Linked List
2.2. display - Prints the elements of linked list from front to end in a single line.
All elements are separated by space
2.3. size - Returns the number of elements in the linked list.
2.4. removeFirst - Removes the first element from Linked List.
2.5. getFirst - Returns the data of first element.
2.6. getLast - Returns the data of last element.
2.7. getAt - Returns the data of element available at the index passed.
2.8. addFirst - adds a new element with given value in front of linked list.
2.9. addAt - adds a new element at a given index.
2.10. removeLast - removes the last element of linked list.
2.11. removeAt - remove an element at a given index.
3. You are required to complete the body of reverseDI function. The function should be an iterative function and should reverse the contents of linked list by changing the "data" property of nodes.
4. Input and Output is managed for you.
Input Format
Input is managed for you
Output Format
Output is managed for you
Question Video
Constraints
None
Sample Input
addFirst 10
addFirst 20
addLast 30
addLast 40
addLast 50
addFirst 60
removeAt 2
display
reverseDI
display
quit
Sample Output
60 20 30 40 50 
50 40 30 20 60


  • Editorial

    The problem deals with reversing the given linked list, here we will use a data iterative approach, i.e. instead of reversing the list, we will modify the elements of the list to get our result. Say for example we have a list 1 -> 2 -> 3 -> 4 -> 5 and we wish to reverse the list (by any approach, as the final output list would not be affected by the type of method used) then our output list will be 5 -> 4 -> 3 -> 2 -> 1.

    We are given a linked list class which has three data members:

    1. Head: It points to the starting node of the linked list.

    2. Tail: It points to the last node of the linked list.

    3. Size: It stores the current length (or size) of the linked list.

    We are also given a getNodeAt() function which returns the node at ith index.

    When we need to reverse a list, deep down what needed to be done is that the last node should be now the first node and the first node should now be the last node. Similarly, the second node and the second last node should also be interchanged, and so on. Now we will implement this approach on linked list data. For that, we will keep a left index (say li) at 0 and a right index (say ri) at size - 1. What we wish to do is to swap the elements at li and ri and update li and ri upto the point when li becomes equal to ri.

    Below is the implementation in Java:

    private Node getNodeAt(int idx) {
                                        Node temp = head;
                                        for (int i = 0; i < idx; i++) {
                                        temp = temp.next;
                                        }
                                        return temp;
                                    }
                                     public void reverseDI() {
                                        int li = 0;
                                        int ri = size - 1;
                                        while(li < ri){
                                        Node left = getNodeAt(li);
                                        Node right = getNodeAt(ri);
                                         int temp = left.data;
                                        left.data = right.data;
                                        right.data = temp;
                                         li++;
                                        ri--;
                                        }
                                    }

    java false

    Dry Run

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

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

    First Iteration

    Here, li = 0 and ri = 4

    Swapping Operation

    temp = leftNode.data = 1

    leftNode.data = rightNode.data = 5

    rightNode.data = temp = 1

    So we have updated our leftNode and rightNode

    Now our list looks like, 5 -> 2 -> 3 -> 4 -> 1

    Updation of li and ri

    li = 1 and ri  = 3

    Second Iteration

    Here, li = 1 and ri = 3

    Swapping Operation

    temp = leftNode.data = 2

    leftNode.data = rightNode.data = 4

    rightNode.data = temp = 2

    So we have updated our leftNode and rightNode

    Now our list looks like, 5 -> 4 -> 3 -> 2 -> 1

    Updation of li and ri

    li= 2 and ri  = 2

    Now when we re-enter while loop the condition fails as now li equals ri and our loop breaks and we return our output. As we can notice here that after the second iteration the list is identical to our output, which verifies our algorithm.

    Points to note here

    1. If we were to run the loop till end instead of till middle then at li == ri we would get our reverse list but moving forward to end we would again have reversed our list and then we would have gotten the original unreversed list as our result.

    2. At li == ri we break the loop as swapping the data at same index changes nothing.

    3. Incrementing li means moving from the first node to the second then to the third and so on.

    4. Decrementing ri means moving from the last node to second last then to third last and so on.

    5. This incrementation and decrementation ensure that we swap correct pairs like the first node with last, the second node with second last, and so on.

    6. The actual time complexity is O(n/2) which is effectively equal to O(n).

    Time Complexity: O(n)

    The time complexity for the function is linear as we need to traverse the entire list to swap every element in the list.

    Space Complexity: O(1)

    The space complexity for the function is constant as we have only used referenced variables in our algorithm.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name