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.
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!
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); }
Yeah it's recursive but it's nothing but changing the same iterative loop in a recursive way. This solution not certainly using dfs as the solution in this video.
no one is a genius, some people just practice more, and a rare few people practice enough that they see new patterns other could not and therefore expand human knowledge with their gained intuition
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.
@@Mr.Fantomblox It was good. Luckily they asked 2 easy questions. String reverse and average of top student from a list of marks. Solved them, got a reject due to hiring freeze. Good experience though!
Yes it was. Most questions come from neetcode or are similar in patterns. I couldn’t clear the interview due to my lack of skills. So working for a faang still remains a goal to achieve
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 = self.reverseListRecursive(head.next) head.next.next = head head.next = None return newHead
I had the same problem when I started LC. Recursion code never made any sense to me. (I'd spend hours trying to understand solutions) You just got to keep brute forcing recursion code and problems and eventually it "clicks"
@@orangethemeow On the way back from recursive calls.... its a quick way of accessing the end-node of the new reversed linked list and make that end-node's next point to the node(head) in the current recursion frame. Not sure if that makes sense... hope below example makes it clear: Input HEAD: 1->2->3->null At the end of recursive calls 3 becomes newHead and it returns from last recursive call... now we have two ways to make 3 point to 2, I will put node value in {} for clarity : A) newHead{3}.next = head{2} OR B) head{2}.next{3}.next = head{2} Now, down the line when it is time for pointing 2 to 1: newHead still points to 3 but we can point node 2 to 1 by using head{1}.next{2}.next = head{1} even though option A worked in the first case, option B will always work down the line as newHead always points to first element in the reversed list i.e 3 in this case.
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;
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(remember we still have 2 3. Now the result is 2 2 and repeat.
Thank you for posting this. You should avoid using if not head: return None because 0 is a falsy value and the method will return None if it is a element contained in the Head Node.
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
Was entirely confused at first as well. He say says in the video that the "if not head" statement is for the base case, but it really is only for the edge case where you're given an empty list (I ran it through some sample solutions on leetcode and all other test cases worked). The real base case is simply evaluated through the "if head.next" part, which will cut subsequent recursive calls if you reach the end of the list i.e. head.next is evaluated as null (or None in Python)
@@alr0495 thanks for this. new to leetcode and spent days trying to understand why there seemed to be 2 bases cases for this recursive solution until i read your comment
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
I have seen a couple shorter ways to do it than neetcode. This is the shortest and most intelligible def reverseList(self, head: Optional[ListNode], prev=None) -> Optional[ListNode]: if head is None: return prev nxt = head.next head.next = prev return self.reverseList(nxt, head)
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
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!
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.
renamed variables + added comments to the recursive solution to make things clearer for myself/hopefully others: def reverseList(self, curr): if not curr: # this is ONLY for if the original test input is empty, doesn't apply in all other cases return None oldTail = curr # keep assigning to curr as we recurse down, then the last one will be the one we actually pass all the way back up if curr.next: oldTail = self.reverseList(curr.next) # stays the same as we recurse back up curr.next.next = curr # this is what actually points next back to curr as we recurse back up curr.next = None # point to None in case we've recursed back up to the old head (new tail now) return oldTail # keep passing all the way up to eventually be the new head
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 .
Spent some time refactoring the answer to make it more "classical" recursion. Hope it helps other people. fun reverseList(head: ListNode?): ListNode? { return if (head == null) { null } else if (head.next == null) { head } else { val newHead = reverseList(head.next) head.next?.next = head head.next = null newHead } }
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
class Solution: def reverseList(self, head: ListNode) -> ListNode: # Recursive answer # Base case: If the list is empty or has only one node, it's already reversed. if not head or not head.next: return head # Recursive call to reverse the remaining part of the linked list. Break it down to sub problems to keep reversing. # reversed_head will be the head of the reversed linked list for the rest of the nodes. reversed_head = self.reverseList(head.next) # At this point, head.next points to the next node in the original list, which will be the last node # in the reversed linked list. We need to make the next node point to the current head node, effectively reversing the link. print(head.next.next) head.next.next = head print(head.next.next.val) # Set the current head's next pointer to None, as it will be the last node in the reversed linked list. head.next = None # Return the new head of the reversed linked list (reversed_head). return reversed_head
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.
Line 16: head.next.next is the one reversing the nodes. It is more like saying point the NEXT to NEXT node to myself. Which means asking the pointer of current head's next node to point to the current head itself, thereby reversing the next node. This would produce a cycle of pointer therefore to break the cycle head.next is set to None in next line.
what about this? def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: c = head while c and c.next: n = c.next c.next = n.next n.next = head head = n return head
def reverseList(head): if (head is None) or (head.next is None): return head newhead = reverseList(head.next) head.next.next = head head.next = None return newhead
Looks like in recursive call the last call in the stack (the one at the bottom with reverseList(1) receives (new) reversed head pointer, and tail pointer. input: head->1->2->3 --stack top reverseList(3) -> 3->nil reverseList(2) -> 3->2->nil reverseList(1) -> 3->2->1->nil --- stack bottom zooming in to the call "reverseList(1)" here: func reverseList(_ head: ListNode?) -> ListNode? { // "head" holds ref to "1" var newHead = head if head?.next != nil { newHead = reverseList(head?.next) // 'newHead->3-2 ; head?.next->2 (notice that 2 is our tail) head?.next?.next = head // set 1 to tail ''newHead->3-2->1 head?.next = nil // it removes the cycle, looks like 2->2 ??? } return newHead }
if (head == null){ return head; } // in- place reversal of linked list ListNode prev = null; ListNode curr = head; while (curr!=null){ prev = new ListNode(curr.val, prev); curr = curr.next; } return prev; is this logically right?
Also, for those who are confused about the code line head.next.next = head. Here’s one explanation to hopefully clarify one line of confusion since I was confused for the longest time :P. So assignment lines of code such as head.next.next = head are executed right to left (get the value of head first and then assign it to head.next.next). Thus in the case after returning from the base case, the stack frame’s head function parameter value at that moment is referring to Node 2. Therefore if head=NODE 2, then (head.next) refers the NODE 3, and then (head.next).next or (NODE 3).next refers to the POINTER of node 3. Be careful NOT to focus too much on the Null/None value of the pointer since that’s where my confusion was. I was thinking head.next.next meant if head = Node2, then head.next=Node3 and then head.next.next = null, so then head.next.next = head translates to null = Node 2. And that’s where my mistake and confusion came in. Long story short, the role of head.next.next is to reverse the order of the nodes and instead of thinking that head.next.next refers to null, think that head.next.next refers to the POINTER of Node3. As a result, head.next.next = head, reassigns the Node2 (head) to Node3's next pointer (head.next.next) or in other words Node3s next pointer is now assigned to point at Node2 which reverses the order.
I think your recursive solution here sacrifices significant readability, but it works lol. I don't understand how your brain works like that lol: class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: def reverse(prev, curr): if curr is None: return prev head = reverse(curr, curr.next) curr.next = prev return head return reverse(None, head)
if not head: return None This condition never executes - the if head.next condition which comes later ensures that head reverseList is never passed a None head However I see that leetcode won't pass it without this condition. I guess that's one of those validation cases where the function is called with None directly?
Maybe this solution will be more readable for somebody: public ListNode ReverseListRecursive(ListNode head) { if (head == null) // edge case - no elements in our list return null; if (head.next == null) // we are at the end of our linked list return head; // so we just return current head var newHead = ReverseListRecursive(head.next); // we reverse sublist starting from next element head.next.next = head; // we change link to next element for next element so it looks at current head head.next = null; // now our current head is at the end for new reversed list so next must be null return newHead; }
How come we can't do newHead.next = node instead of head.next.next = head? Doing this gives the wrong answer but logically it seems to be the same thing to me..=(
Here's how head.next.next = head works From the video we want the lastNode/tail of the reversed node to point of the current node. head.next is tailNode (of reversedList) head.next.next is tailNode.next head.next.next = head is taiilNode.next = head. ---------------------------------------------------- Easier Version of Code: ``` def reverseList(node) : if not node: return newHead = head if head.next: newHead = reverseList(head.next) tailNode = head.next tailNode.next = head head.next = None return newHead; ```
the hardest thing to grasp here is how you return a new head while manipulating the existing linked list. its giving me a headache. this is one of those solution where i would say recursion is not the ideal method for it.
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?
when we assign to newHead variable recursive call function (line 15)- will it automatically start new recursive call? or it will skip this line to next - 16 line?
it will keep starting new recursive calls until it hits the base case (if head.next is None) at which point it'll execute line 17 (assigning head.next to None) and will execute line 19 (returning newHead)
Anyone having this Problem? next not defined? Or optional not defined? Or Listnode not defined? Try this: from typing import Optional class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def reverseList(self, head: ListNode) -> ListNode: current = ListNode(val=head) prev = None while current: temp = current.next current.next = prev prev = current current = temp return prev
Hi,This is rohini.I was tried the below code for reversing a linked list. but it shows error like non-type object has no attribute ' next'. I didn't get what the error is dummy=ListNode() dummy1=dummy while head: tail=head while tail.next.next: tail=tail.next dummy.next=tail dummy=dummy.next tail.next=None return dummy1.next
because the two pointers march through the nodes such that prev starts with None and head starts with the first node, so when the loop finishes, prev points to the last node and head points to None, so we definitely need to return prev as the new head (in the last iteration prev gets updated to the last node and the head gets updated as None)
Can anyone please tell me, how to code this program on a locally installed version of python. I mean, in neet/leet code, linked lists are predefined. I can't solve this problem on my local pc, without defining a list first.
@@NeetCode you could also check if head or head.next is None in the base case and return the head if it is since you'd be at the input list's tail which would be the new head. After that, the function would just be the four lines under the if statement.
i understand your recursion approach but i think it's way complicate due to head.next = None just effectively need to use 1 time Other approach in coment much reachable
Why can't I just reverse the list using slicing? I'm still pretty new to coding, but it seems hella easier to just type out head[::-1] and call it a day. I'm guessing it has something to do with the time complexity?
spent 20 minutes trying to figure out how to do this with 2 pointers as advertised @1:10 only to find that you actually use a 3rd in the implementation lol
One more solution (js) We go through list to the end and do all job at bubbling phase var reverseList = function(head) { function reverse(prev, current) { if (!current) { return prev; } const head = reverse(current, current.next); current.next = prev; return head; } return reverse(null, head); };
@@saugatgarwa6389 I don't think so. There is a recursive call for each element `n`, hence `n` function calls on the stack. Please correct me if I'm wrong.
@@PippyPappyPatterson Yes, you're correct. I mentioned the time and space complexity for the Iterative method cuz that seemed the most understandable and efficient to me :D
i understood it finally so here is a breakdown, when the recursive method reaches the base case which is 4 and returns 4 as a new head, the newhead will be 4 and the head will be 3 that is because the recursive method is backtracking or unwinding, at first 1->2->3->4->none right. in this case head.next.next = head will be 3->4->3 because head.next is 4 for head=3 and head.next.next will replace none and become 3->4->3. and then head.next=none will unlink the 3 from behind so it will become 4->3->none. do you get the idea now you can see the pattern of how the reverse link is forming. so now we manipulated the original list for head=3 right, now when the recursive method goes to next frame which is head=2, now it will meet the new partially reversed link and and its own link using head 2 which will be 2->3>4>none, so it will asses 2.next.next which is basically 3.next because next.next means the pointer after thesecond pointer. we know 3.next points to none from the reversed link 4->3->none, so now 3.next will be 4>3>2 because we assigned head=2 with this line of code head.next.next = head, 3next =2 so the reversed link would be 4->3->2->none. so for head=3 with the first iteration of the unwinding which is head=3 and the base case orthe newhead=4. the first one you basically will extend the original link to the right for the itearation of the unwinding taking the link from 1->2->3->4->none and then it will become 1->2->3->4->3 and then you will unlink it using head.next = None and then it will become 4->3->none and then 2.next.next equals 3.next but since we manioulated the reverse link, 3.next will assign head=2 to head.next.next adding 2 to the reverse link and then it will become 4->3->2->none. same process for head=1, the tricky part is understanding how for head 3 we only got the original link and for head=2 we got both the original and reversed link. Also try to learn how recursion technique works it will reach the base case in this case 4 and then it will unwind the first undwinging will be head=3
It is not clear at all - what is the head? without roting/memorizing, can u tell what is the type of input head? No, it is not a listnode. because if u do print(head.data) it will throw an error....so what is it?
The recursive solution was so unbelievably hard to understand, I tried to draw it out and everything. I could not, just look at the comments, its a much more efficient approach for understanding and saving time. No offense. The iterative solution was good though!
At the end, current will be None because when we're reversing we go to the next element in each iteration and in a case like this: 1 -> 2 -> 3 -> 4 -> None Once it goes to 4 and reverses it, in the same iteration it'll set curr to None. BUT None's previous node is 4 which we can use as the node.
@Alexander. As you can see we are passing "head.next" recursively to recreverseList(self, head). According to our condition, if head == None or head.next == None return head. That is after passing "head.next" recursively we get, if "head.next.next == None" return head, which is our second last node. Then we proceed further for reversing the list.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Can you tell me in which occasion does reverse linked list are used...?
@@enriquewilliams8676 Coding interviews
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.
Yooo this solution is fire.Thank you so much dude
Amazing solution!
Uses iterative code lines, nice
Easiest recursive to understand.
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(prev, curr):
if not curr: return prev
tmp = curr.next
curr.next = prev
return reverse(curr, tmp)
return reverse(None, head)
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!
Thank you ✌️
Interestingly, the recursive function made a million times more sense to me.
Yea it's honestly making me feel like an idiot
you can do iteration if you wany, but recursive concept is important to understand in your career path
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);
}
That’s much easier to digest! Thanks for sharing
After spending a long time to understand Neetcode's recursion, yours took like 1 min to understand. thanks for sharing another way!
Thanks, this comment is worth pining
Yeah it's recursive but it's nothing but changing the same iterative loop in a recursive way. This solution not certainly using dfs as the solution in this video.
i lost hope in understanding the recursive solution and then saw your comment. thank you Josh,
I have struggled so much on this simple problem. You explained it so simply. You are genius thanks for that !
no one is a genius, some people just practice more, and a rare few people practice enough that they see new patterns other could not and therefore expand human knowledge with their gained intuition
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.
Can I ask how your interview went?
@@Mr.Fantomblox It was good. Luckily they asked 2 easy questions. String reverse and average of top student from a list of marks. Solved them, got a reject due to hiring freeze. Good experience though!
@@Inconvenient-MRKim May I ask if this was a faang company?
Yes it was. Most questions come from neetcode or are similar in patterns. I couldn’t clear the interview due to my lack of skills. So working for a faang still remains a goal to achieve
Hey, what's up? Did you get to faang?
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 = self.reverseListRecursive(head.next)
head.next.next = head
head.next = None
return newHead
i still struggle with the recursion code ... i can understand the logic, but not the code... sigh. Thanks for sharing!
try to understand this you might get this code:
def reverseList(self, head: ListNode) -> ListNode:
if head == None or head.next == None:
return head
newHead = self.reverseList(head.next)
head.next.next = head
head.next = None
return newHead
I had the same problem when I started LC. Recursion code never made any sense to me. (I'd spend hours trying to understand solutions)
You just got to keep brute forcing recursion code and problems and eventually it "clicks"
@@tanayshah275 I'm having issue understanding head.next.next = head
@@orangethemeow On the way back from recursive calls.... its a quick way of accessing the end-node of the new reversed linked list and make that end-node's next point to the node(head) in the current recursion frame. Not sure if that makes sense... hope below example makes it clear:
Input HEAD: 1->2->3->null
At the end of recursive calls 3 becomes newHead and it returns from last recursive call...
now we have two ways to make 3 point to 2, I will put node value in {} for clarity :
A) newHead{3}.next = head{2}
OR
B) head{2}.next{3}.next = head{2}
Now, down the line when it is time for pointing 2 to 1:
newHead still points to 3 but we can point node 2 to 1 by using
head{1}.next{2}.next = head{1}
even though option A worked in the first case, option B will always work down the line as newHead always points to first element in the reversed list i.e 3 in this case.
@@rockstars369 Thank you! The 'head.next.next' confused the heck out of me. Putting number next to it makes it way easier to understand!
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)
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;
}
-------------------------------------------------------------------------
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(remember we still have 2 3.
Now the result is 2 2 and repeat.
Loved this explanation. I didn't completely understand the video. Thank you so much!
Thank you so much, I was very confused because of that. Your explanation was amazing and easy to understand.
OMG Ty very much
Thank you so much! Now i understand
Thank you so much...
Thank you for posting this.
You should avoid using
if not head:
return None
because 0 is a falsy value and the method will return None if it is a element contained in the Head Node.
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
Was entirely confused at first as well. He say says in the video that the "if not head" statement is for the base case, but it really is only for the edge case where you're given an empty list (I ran it through some sample solutions on leetcode and all other test cases worked). The real base case is simply evaluated through the "if head.next" part, which will cut subsequent recursive calls if you reach the end of the list i.e. head.next is evaluated as null (or None in Python)
@@alr0495 thanks for this. new to leetcode and spent days trying to understand why there seemed to be 2 bases cases for this recursive solution until i read your comment
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
I have seen a couple shorter ways to do it than neetcode. This is the shortest and most intelligible
def reverseList(self, head: Optional[ListNode], prev=None) -> Optional[ListNode]:
if head is None:
return prev
nxt = head.next
head.next = prev
return self.reverseList(nxt, head)
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
bro your explanation helped a lot thanks man
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!
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
return self.recursive(None, head)
def recursive(self, prev: ListNode, curr: ListNode):
if not curr:
return prev
newNext = curr.next
curr.next = prev
return self.recursive(curr, newNext)
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.
Simple!!!
# Recursive
def reverseList(self, head):
if not head or not head.next:
return head
nextNode = head.next
reverseHead = self.reverseList(nextNode)
nextNode.next = head
head.next = None
return reverseHead
# Iterative
def reverseList(self, head):
prev = None
while head:
temp = head.next
head.next = prev
prev = head
head = temp
return prev
```
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head == None or head.next == None:
return head
newHead = self.reverseList(head.next)
front = head.next
front.next=head
head.next= None
return newHead
````
renamed variables + added comments to the recursive solution to make things clearer for myself/hopefully others:
def reverseList(self, curr):
if not curr: # this is ONLY for if the original test input is empty, doesn't apply in all other cases
return None
oldTail = curr # keep assigning to curr as we recurse down, then the last one will be the one we actually pass all the way back up
if curr.next:
oldTail = self.reverseList(curr.next) # stays the same as we recurse back up
curr.next.next = curr # this is what actually points next back to curr as we recurse back up
curr.next = None # point to None in case we've recursed back up to the old head (new tail now)
return oldTail # keep passing all the way up to eventually be the new head
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 .
Spent some time refactoring the answer to make it more "classical" recursion. Hope it helps other people.
fun reverseList(head: ListNode?): ListNode? {
return if (head == null) {
null
} else if (head.next == null) {
head
} else {
val newHead = reverseList(head.next)
head.next?.next = head
head.next = null
newHead
}
}
Every time i'm amazed by how much you can simplify solutions and how well you can explain thank you for all that
Stucked with recursive way? See this example:
a -> b
"head.next" is (b) right?
So I want my "b.next" pointing to previous!
a
your tutorials help a lot..thankyou!!
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
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# Recursive answer
# Base case: If the list is empty or has only one node, it's already reversed.
if not head or not head.next:
return head
# Recursive call to reverse the remaining part of the linked list. Break it down to sub problems to keep reversing.
# reversed_head will be the head of the reversed linked list for the rest of the nodes.
reversed_head = self.reverseList(head.next)
# At this point, head.next points to the next node in the original list, which will be the last node
# in the reversed linked list. We need to make the next node point to the current head node, effectively reversing the link.
print(head.next.next)
head.next.next = head
print(head.next.next.val)
# Set the current head's next pointer to None, as it will be the last node in the reversed linked list.
head.next = None
# Return the new head of the reversed linked list (reversed_head).
return reversed_head
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.
Line 16: head.next.next is the one reversing the nodes. It is more like saying point the NEXT to NEXT node to myself. Which means asking the pointer of current head's next node to point to the current head itself, thereby reversing the next node. This would produce a cycle of pointer therefore to break the cycle head.next is set to None in next line.
what about this?
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
c = head
while c and c.next:
n = c.next
c.next = n.next
n.next = head
head = n
return head
You make it seem effortless. ❤️
def reverseList(head):
if (head is None) or (head.next is None):
return head
newhead = reverseList(head.next)
head.next.next = head
head.next = None
return newhead
Looks like in recursive call the last call in the stack (the one at the bottom with reverseList(1) receives (new) reversed head pointer, and tail pointer.
input: head->1->2->3
--stack top
reverseList(3) -> 3->nil
reverseList(2) -> 3->2->nil
reverseList(1) -> 3->2->1->nil
--- stack bottom
zooming in to the call "reverseList(1)" here:
func reverseList(_ head: ListNode?) -> ListNode? { // "head" holds ref to "1"
var newHead = head
if head?.next != nil {
newHead = reverseList(head?.next) // 'newHead->3-2 ; head?.next->2 (notice that 2 is our tail)
head?.next?.next = head // set 1 to tail ''newHead->3-2->1
head?.next = nil // it removes the cycle, looks like 2->2 ???
}
return newHead
}
if (head == null){
return head;
}
// in- place reversal of linked list
ListNode prev = null;
ListNode curr = head;
while (curr!=null){
prev = new ListNode(curr.val, prev);
curr = curr.next;
}
return prev;
is this logically right?
For those confused about head.next.next. Basically just think of it as pointing from the next node to pointing to itself.
Also, for those who are confused about the code line head.next.next = head. Here’s one explanation to hopefully clarify one line of confusion since I was confused for the longest time :P. So assignment lines of code such as head.next.next = head are executed right to left (get the value of head first and then assign it to head.next.next). Thus in the case after returning from the base case, the stack frame’s head function parameter value at that moment is referring to Node 2. Therefore if head=NODE 2, then (head.next) refers the NODE 3, and then (head.next).next or (NODE 3).next refers to the POINTER of node 3. Be careful NOT to focus too much on the Null/None value of the pointer since that’s where my confusion was. I was thinking head.next.next meant if head = Node2, then head.next=Node3 and then head.next.next = null, so then head.next.next = head translates to null = Node 2. And that’s where my mistake and confusion came in. Long story short, the role of head.next.next is to reverse the order of the nodes and instead of thinking that head.next.next refers to null, think that head.next.next refers to the POINTER of Node3. As a result, head.next.next = head, reassigns the Node2 (head) to Node3's next pointer (head.next.next) or in other words Node3s next pointer is now assigned to point at Node2 which reverses the order.
@@kevinchen1570 great!!!!
I think your recursive solution here sacrifices significant readability, but it works lol. I don't understand how your brain works like that lol:
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(prev, curr):
if curr is None:
return prev
head = reverse(curr, curr.next)
curr.next = prev
return head
return reverse(None, head)
if not head:
return None
This condition never executes - the if head.next condition which comes later ensures that head reverseList is never passed a None head
However I see that leetcode won't pass it without this condition. I guess that's one of those validation cases where the function is called with None directly?
cause the list could be empty
@@xenomagpie4484 my man
Maybe this solution will be more readable for somebody:
public ListNode ReverseListRecursive(ListNode head)
{
if (head == null) // edge case - no elements in our list
return null;
if (head.next == null) // we are at the end of our linked list
return head; // so we just return current head
var newHead = ReverseListRecursive(head.next); // we reverse sublist starting from next element
head.next.next = head; // we change link to next element for next element so it looks at current head
head.next = null; // now our current head is at the end for new reversed list so next must be null
return newHead;
}
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode node1=null;
while(head!=null)
{
node1=new ListNode(head.val,node1);
head=head.next;
}
return node1;
}
}
Better recursive solution in C++
Node* reverseList(Node* head, Node* previousNode = nullptr){
if(head==nullptr){
return previousNode;
}
Node* newHead {reverseList(head->next, head)};
head->next = previousNode;
return newHead;
}
// using recursion in c#
public ListNode ReverseList(ListNode? curr, ListNode? prev = null) {
if (curr == null) return prev;
var tmp = curr.next;
curr.next = prev;
return ReverseList(tmp, curr);
}
Awesome explanation
Glad it was helpful!
Thank you very much man
@NeetCode What are you using for a tablet/whiteboarding software?
How come we can't do newHead.next = node instead of head.next.next = head? Doing this gives the wrong answer but logically it seems to be the same thing to me..=(
actually your base case won't be reached as you also check next against null before calling the function
Here's how head.next.next = head works
From the video we want the lastNode/tail of the reversed node to point of the current node.
head.next is tailNode (of reversedList)
head.next.next is tailNode.next
head.next.next = head is taiilNode.next = head.
----------------------------------------------------
Easier Version of Code:
```
def reverseList(node) :
if not node:
return
newHead = head
if head.next:
newHead = reverseList(head.next)
tailNode = head.next
tailNode.next = head
head.next = None
return newHead;
```
Hi, can you please elaborate why you did cure.next = prev?
Thank you very much
curr.next should point back so prev holds the pointer to previous pointer
try to make a visual representation once on paper it helps a lot.
Explained it much better than Geeks for Gekks
the hardest thing to grasp here is how you return a new head while manipulating the existing linked list. its giving me a headache. this is one of those solution where i would say recursion is not the ideal method for it.
Great Explanation
Thanks!
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?
yeah.
why do we have to create another reference to the head node using current? Can't we just use head?
when we assign to newHead variable recursive call function (line 15)- will it automatically start new recursive call? or it will skip this line to next - 16 line?
it will keep starting new recursive calls until it hits the base case (if head.next is None) at which point it'll execute line 17 (assigning head.next to None) and will execute line 19 (returning newHead)
HUGE THANKS!
Anyone having this Problem?
next not defined?
Or optional not defined?
Or Listnode not defined?
Try this:
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
current = ListNode(val=head)
prev = None
while current:
temp = current.next
current.next = prev
prev = current
current = temp
return prev
Really good explanation! Thank you
Hi,This is rohini.I was tried the below code for reversing a linked list. but it shows error like non-type object has no attribute ' next'. I didn't get what the error is
dummy=ListNode()
dummy1=dummy
while head:
tail=head
while tail.next.next:
tail=tail.next
dummy.next=tail
dummy=dummy.next
tail.next=None
return dummy1.next
why do we return prev in the iterative solution, are we normally just supposed to return the head?
because the two pointers march through the nodes such that prev starts with None and head starts with the first node, so when the loop finishes, prev points to the last node and head points to None, so we definitely need to return prev as the new head (in the last iteration prev gets updated to the last node and the head gets updated as None)
Can anyone please tell me, how to code this program on a locally installed version of python. I mean, in neet/leet code, linked lists are predefined. I can't solve this problem on my local pc, without defining a list first.
For your recursive solution, why is the memory complexity O(n)?
Recursion call stack takes up memory
On Line 17, shouldn't this be inside the if condition? outside the if, head.next is null already.
Good point! somehow i missed that, but luckily the code works whether we put it inside or leave it outside the if-condition.
@@NeetCode you could also check if head or head.next is None in the base case and return the head if it is since you'd be at the input list's tail which would be the new head. After that, the function would just be the four lines under the if statement.
thank you sir
all i can say is thank uuuuuuuu
How while curr can run if its equal to None ?
Can someone explain why in recursion solution newHead is changing when head is changing?
i understand your recursion approach but i think it's way complicate due to head.next = None just effectively need to use 1 time
Other approach in coment much reachable
Why can't I just reverse the list using slicing? I'm still pretty new to coding, but it seems hella easier to just type out head[::-1] and call it a day. I'm guessing it has something to do with the time complexity?
Go and find out what is a linked list first
A linked list is not the same as a "list" in python, which is actually a dynamic array
That recursive solution was extremely confusing
@NeetCode, Thanks for putting this video but I think Line #13: newHead = Head is not required at all.
It is much more easier to use one line assignment: curr.next, prev, curr = prev, curr, curr.next
i got it by myself (39ms py3), but my god i had to rewire my brain for 30 minutes by talking myself through it
that was helpful
spent 20 minutes trying to figure out how to do this with 2 pointers as advertised @1:10 only to find that you actually use a 3rd in the implementation lol
why do we need a curr pointer. cant we just use head as is?
watch in 1.5x
i felt confused why we need to store in a temporary variable
nxt=curr.next
One more solution (js)
We go through list to the end and do all job at bubbling phase
var reverseList = function(head) {
function reverse(prev, current) {
if (!current) {
return prev;
}
const head = reverse(current, current.next);
current.next = prev;
return head;
}
return reverse(null, head);
};
If I have (head = 1234), then won't doing (head.next.next= head) make (head = 121234) ???
It creates a cycle 1-2-1-2-1....
nxt is the 3rd pointer. So its a three pointer problem, isn't it???
why are you returning prev in two pointer approach?
because cur will be null at the end of the loop
still not understanding the recursive method
Is this the complexity?
O(n) time
O(n) space
It is done in
O(N) time
O(1) space
@@saugatgarwa6389 I don't think so. There is a recursive call for each element `n`, hence `n` function calls on the stack. Please correct me if I'm wrong.
@@PippyPappyPatterson Yes, you're correct. I mentioned the time and space complexity for the Iterative method cuz that seemed the most understandable and efficient to me :D
@@saugatgarwa6389 Ahh, that makes sense. Agreed on the iterative implementation!
that head.next.next = head confuses me everytime
i understood it finally so here is a breakdown, when the recursive method reaches the base case which is 4 and returns 4 as a new head, the newhead will be 4 and the head will be 3 that is because the recursive method is backtracking or unwinding, at first 1->2->3->4->none right. in this case head.next.next = head will be 3->4->3 because head.next is 4 for head=3 and head.next.next will replace none and become 3->4->3. and then head.next=none will unlink the 3 from behind so it will become 4->3->none. do you get the idea now you can see the pattern of how the reverse link is forming. so now we manipulated the original list for head=3 right, now when the recursive method goes to next frame which is head=2, now it will meet the new partially reversed link and and its own link using head 2 which will be 2->3>4>none, so it will asses 2.next.next which is basically 3.next because next.next means the pointer after thesecond pointer. we know 3.next points to none from the reversed link 4->3->none, so now 3.next will be 4>3>2 because we assigned head=2 with this line of code head.next.next = head, 3next =2 so the reversed link would be 4->3->2->none. so for head=3 with the first iteration of the unwinding which is head=3 and the base case orthe newhead=4. the first one you basically will extend the original link to the right for the itearation of the unwinding taking the link from 1->2->3->4->none and then it will become 1->2->3->4->3 and then you will unlink it using head.next = None and then it will become 4->3->none and then 2.next.next equals 3.next but since we manioulated the reverse link, 3.next will assign head=2 to head.next.next adding 2 to the reverse link and then it will become 4->3->2->none. same process for head=1, the tricky part is understanding how for head 3 we only got the original link and for head=2 we got both the original and reversed link. Also try to learn how recursion technique works it will reach the base case in this case 4 and then it will unwind the first undwinging will be head=3
I completed this without any help in just 4 hours😅
iterative solution more intuitive then recursive for this problem
It is not clear at all - what is the head? without roting/memorizing, can u tell what is the type of input head? No, it is not a listnode. because if u do print(head.data) it will throw an error....so what is it?
doesn't it require the return type to be a listNode and since data is an integer, it is an error?
The recursive solution was so unbelievably hard to understand, I tried to draw it out and everything. I could not, just look at the comments, its a much more efficient approach for understanding and saving time. No offense. The iterative solution was good though!
Great explanation! Quick question - why do we return "prev" at the end rather than just the "curr" node if the "curr" node should be reversed?
@Alexander In the iterative solution, "curr" will be null/none at the end, and "prev" will be the new head node/original tail node.
At the end, current will be None because when we're reversing we go to the next element in each iteration and in a case like this:
1 -> 2 -> 3 -> 4 -> None
Once it goes to 4 and reverses it, in the same iteration it'll set curr to None. BUT None's previous node is 4 which we can use as the node.
@Alexander. As you can see we are passing "head.next" recursively to recreverseList(self, head).
According to our condition,
if head == None or head.next == None
return head.
That is after passing "head.next" recursively we get,
if "head.next.next == None"
return head, which is our second last node.
Then we proceed further for reversing the list.
I do not like this question as all the solutions are in-place, ie modifying input, while it was not mentioned in description and not obvious
That head.next.next is confusing AF.
helpful
can anyone explains head.next.next step?
Can someone explain the recursive code
Just create a new list,
then add each node of the old list, one by one from head to tail, to the front of the new list.
Recursion makes me wanna puke
@@irispallis brain gave me 500 error code
@@alexandroskourtis5268
def study_recursion(puke):
if puke == 0:
print('Congrats, you are done with recursion')
return
puke -= 1
study_recursion(puke)
Shouldn't the recursive solution begin with "while head.next" instead of "if head.next" - otherwise the branch executes once?
No. Otherwise it's iterative problem all over again. Also that is base case
3 pointers solution not 2)