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