How To Reverse A Singly Linked List | The Ultimate Explanation (Iteratively & Recursively)
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
This is a classic interview problem for 1st and 2nd year interviews. I got this question in my interview for the Explore Microsoft Program.
Very simple. But we will still do this.
This is what I call a utility problem. Utility problems don't test your ability to think, they test your ability to do things such as traverse or manipulate data structures in often trivial (but not always) ways.
The brute force for this is to copy the linked list into a static structure like an array and then create a linked list from that...nah.
So the 2 ways we will really do it is to move the pointers around
Way 1 (Iterative):
For this approach we need to keep track of a prev and curr node. Why? This list is singly-linked so we can't get a node's predecessor, so during the traversal we must remember who came before the node we are at.
Before doing any of that we save the next node's address since if we move the node we are at's address, we would lose where to go next in the traversal.
Then finally we set the current node to the next node that we saved at the start of the iteration.
Complexities:
Time: O(n)
Space: O(1)
Way 2 (Recursive):
This is "top down" recursion, we start at the top and drill down. Then when we reach the bottom (the base case) we will come back upwards with the answer.
The recursive code will drill down in recursive calls until we get to the base case.
The base case gets triggered when the current node has no next, this means we are at the list's end, in that case we just return the node passed into the call.
Then the node before the last node has itself and the last node to work with.
We do some pointer movement.
Last node points to curr.
curr pointer to null since we don't know if this is the first node in the list.
first node will end up the last node in the list.
Then we return the head of the new linked list on the way back upwards.
The we repeat, what we get from the recursive call is a reversed list, we append our node to that list, and then return back upwards with an even longer reversed list.
In the top call we say:
"Reverse the rest of the list"
"Reverse the rest of the list"
"Reverse the rest of the list"
I'm the last node "Here I am 2nd to last node"
"processing"
3rd to last gets a reversed list, append
4th to last gets a reversed list, append
......and so on
Complexities:
Time: O(n)
Space: O(n)
Call stack space used.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
Watch video How To Reverse A Singly Linked List | The Ultimate Explanation (Iteratively & Recursively) online without registration, duration hours minute second in high quality. This video was added by user Back To Back SWE 18 December 2018, don't forget to share it with your friends and acquaintances, it has been viewed on our site 162,13 once and liked it 5.2 thousand people.