Reverse Linked List (pointer 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 reversePI function. The function should be an iterative function and should reverse the contents of linked list by changing the "next" 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
reversePI
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 pointer iterative approach, i.e. we will modify our list to reverse it and we would not change the node data. 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.

    There can be two ways to reverse a linked list:


    The difference in both these methods is that in the data iterative method we are not changing the linked list orientation, we were only replicating the output elements whereas in the pointer iterative approach we aim to redesign our list to reverse it.

    The idea behind the pointer iterative is to simply point all nodes to its previous nodes. This can be implemented by having two pointers, one for storing the previous node and the other for storing the next node, so that for every node the current node can point to the previous node and then can move forward to the next node. The next node is needed to prevent data loss due to the reassignment of the next data member of the current node.

    Below is the implementation in Java:

    public void reversePI(){
                                        if(size <= 1){
                                        return;
                                        }
                                         Node prev = null;
                                        Node curr = head;
                                        while(curr != null){
                                        Node next = curr.next;
                                        curr.next = prev;
                                        prev = curr;
                                        curr = next;
                                        } 
                                        Node temp = head;
                                        head = tail;
                                        tail = temp;
                                    }

    java false

    Dry Run

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

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

    First Iteration

    Here, currNode = head, prevNode = null and nextNode = curr.next

    CurrNode.next = prevNode = null

    prevNode = currNode = 1st Node

    currNode = nextNode = 2nd Node

    List: null <- 1(prevNode) ......2(currNode) -> 3 -> 4 -> 5

    Second Iteration

    Here, currNode = 2nd Node, prevNode = 1st Node and nextNode = curr.next = 3rd Node

    CurrNode.next = prevNode = 1st Node

    prevNode = currNode = 2nd Node

    currNode = nextNode = 3rd Node

    List: null <- 1 <-  2(prevNode) ...... 3(currNode) -> 4 -> 5

    Third Iteration

    Here, currNode = 3rd Node, prevNode = 2nd Node and nextNode = curr.next = 4thNode

    CurrNode.next = prevNode = 2ndNode

    prevNode = currNode = 3rdNode

    currNode = nextNode = 4thNode

    List: null <- 1 <-  2<- 3(prevNode) ......4(currNode) -> 5

    Fourth Iteration

    Here, currNode = 4thNode, prevNode = 3rdNode and nextNode = curr.next = 5thNode

    CurrNode.next = prevNode = 3rdNode

    prevNode = currNode = 4thNode

    currNode = nextNode = 5thNode

    List: null <- 1 <-  2 <- 3<- 4(prevNode) ...... 5(currNode)

    Fifth Iteration

    Here, currNode = 5thNode, prevNode = 4thNode and nextNode = curr.next = null

    CurrNode.next = prevNode = 4thNode

    prevNode = currNode = 5th Node

    currNode = nextNode = null

    List: null <- 1 <-  2 <- 3 <- 4<- 5

    Sixth Iteration

    As currNode == null, loop breaks.

    Our final list,

    head -> 1 <-  2 <- 3 <- 4 <- 5<- tail

    As head and pointers are at wrong positions we need to swap them, after swapping,

    head -> 1 -> 2 -> 3 -> 4 -> 5 <- tail

    Time Complexity: O(n)

    The time complexity for the function is linear as we need to traverse the entire list to change its orientation (or next data member re-allocation).

    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