Reverse Linked List - Iterative AND Recursive - Leetcode 206 - Python

0:00 - Read the problem
0:50 - Drawing Iterative
3:00 - Coding Iterative
4:48 - Drawing Recursive
8:15 - Coding Recursive

leetcode 206

[Extremesarova]

Maybe this recursive solution can make things clearer for you, guys

def reverseListRecursive(self, head):
def reverse(cur, prev):
if cur is None:
return prev
else:
next = cur.next
cur.next = prev
return reverse(next, cur)

return reverse(head, None)

Also, I think that we are using three pointers here: prev, cur and next.

[mobaisi]

Unfortunately the recursive code doesn't make much sense. Pretty much all the variants in the comments are much easier to digest. The iterative solution was great though!

[Inconvenient-MRKim]

Dude! Thank you so much. I'm preping for my interviews through your 150 questions and was struggling with this basic idea of reversing for a long time. You making videos of even such easy questions and concepts helps a lot. I really appreciate all your help and efforts taken for making the website and videos.

[manishmaharjann]

I have struggled so much on this simple problem. You explained it so simply. You are genius thanks for that !

[joshbouganim]

Passing in a prev node to the recurse call makes the logic much more easier to grasp and mimics the logic of the iterative solution.


public ListNode ReverseList(ListNode head) {
return Recurse(null, head);
}

public ListNode Recurse(ListNode prev, ListNode cur){
if(cur == null) return prev;

//save new next node
var newNext = cur.next;

//reverse
cur.next = prev;

//reverse rest of the list
return Recurse(cur, newNext);
}

[ax]

i still struggle with the recursion code ... i can understand the logic, but not the code... sigh. Thanks for sharing!

[KSMuralidhar]

Nice answer . multiple new_head assignment is bit confusing.

practically, if head is null(in case of empty list) or head.next is null will marked as root.

so we can easily stop recursion at last node and keep reversing list without much confusion.
this approach has similar time and space requirements(in terms of leet code as well as big oh. infact it's quite better).
code below
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null ) return head;


ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;

return newHead;
}

[jagggyjazz]

Bro cleared my confusion in an instant, got the logic but I made a silly mistake of things prev as something similar to curr.nxt, but it is similar to the temp variable nxt. Was scratching my head to interchange 1 line of code. I love this.

[JimmyCheng]

the recursive solution is mind-buggling but it is the essence of a recursive funciton, basically throw the problem at the computer and let it do the work

[eshaanmehta]

Would another valid solution be to create a new head node. And continuously pop the first node from the original list and push front to the new list until the original head is null. Then return the new head. Wouldn’t this also have a TC of O(n) and SC of O(1)? Please if I am mistaken I appreciate any corrections, I am new to learning data structures. Thanks!

[Saotsu]

My simple recursive solution:
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
def r(prev, node):
if not node:
return prev

first = r(node, node.next)
node.next = prev

return first

return r(None, head)

[the-tankeur]

Every time i'm amazed by how much you can simplify solutions and how well you can explain thank you for all that

[khoantum]

head.next.next = head explanation:

linkedlist of 1 => 2 => 3

base case focuses on 2 => 3 where 2 is the head

Head.next.next = head means 3.next = 2 (the head) so this makes a 2 => 3 circular linked list (which means 2 => 3 & 2 <= 3 exists). 2 is still the head.

then we must detach 2 => 3(remember we still have 2 <= 3) so head.next = null means we detach 2 => 3.

Now the result is 2 <= 3.

Now we go to the next part which is 1 => 2 and repeat.

[bruce]

Hope this is helpful.

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

# Edge case, in case input head is None, that is 0 node.
if not head:
return None

# Both base case and edge case.
# Edge case, if input head has 1 Node only
# Base case, because the last node does not have next Node, the last node will return self as lastNode.
lastNode = head

# Recursive case
if head.next:

# This line always return the last node no matter which stack you are at.
lastNode = self.reverseList(head.next)

# This is more like 1 -> 2 -> None
# turn into >>> 1 -> 2 -> 1, now the Node(2).next points to Node(1) which is reversed now
head.next.next = head

# For line above, in case there is a cycle
head.next = None

# for example
# 1 > 2 > 3, every stack return Node(3)
# 1 > 2, every stack return Node(2)
return lastNode

[spencerfitzgerald]

The confusing part with his recursive solution is that the base case he calls out is incorrect. The base case he has is actually the edge case when no node is passed into the function. Try throwing in a print statement and you'll see that it's only run when the input is None:
if not head:
print('This is the edge case when the input is None')
return None

Really, the base case is when "head.next == None" (in Python speak "if not head.next"). I rewrote the recursive solution with the base case more apparent:
def reverseListRecursive(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
print('This is the edge case when the input is None')
return None

if not head.next:
print('This is the base case. At this point, we are at the last node in the list.')
newHead = head
else:
newHead =
head.next.next = head
head.next = None

return newHead

[sujalkumarsinha]

I was returning curr when doing this on my own and kept wondering why it won't work when I should've returned prev smh. Thanks for explaining this in an easy manner .

[EatingGuo]

can someone tell me how does it make the nodes after first node reverse by using newhead = reverselist(self.next). i dont see body in the def reverselist. author didnt explain this part.

[brandonwilcox]

Thank you for this explanation. I have a lot of difficulty visualizing recursive problems so this was very helpful.

Though for your iterative solution, wouldn't that technically be a 3 pointer solution due to the addition of the next variable?

[shreerambhat]

or another solution(but not the most optimal) is to use stack. as we traverse to the end we can store it in stack, and then use it.i.e in loop till stack is not empty:
currenthead.next =stack.pop()
currenthead=currenthead.next

[jasonxb]

POINT OF CONFUSION 1:
Leetcode gives an example where it represents a linked list in the form of an array (misleading)

- Your function is not supposed to accept arrays
- It's supposed to accept a linked list as objects linked together with next properties

You can construct a linked list using the constructor function they provide commented out in their built in code editor
They generate linked lists behind the scenes to test your function out

POINT OF CONFUSION 2:
The head parameter in your function is just the linked list in its entirety
The list begins at a certain object, so that's they they refer to it as the head