Can you tell me in which occasion does reverse linked list are used...?

@@enriquewilliams8676 Coding interviews

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)

Thank you ✌️

Interestingly, the recursive function made a million times more sense to me.

Yea it's honestly making me feel like an idiot

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,

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

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!

bro your explanation helped a lot thanks man

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)

Glad it was helpful!

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.

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)

yeah.

cause the list could be empty

@@xenomagpie4484 my man

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.

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)

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.

Recursion call stack takes up memory

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!!!!

It creates a cycle 1-2-1-2-1....

@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.

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...

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!

@@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)

No. Otherwise it's iterative problem all over again. Also that is base case

The "root" is the root node of the new reversed linkedList. So there are two task of reverseList method 1. Propagate the "root" Node in the recursive chain 2. Fix the node pointing at each other. - i.e The head is the "previous node" and we get the next node from head. Then the nextNode will point back to head (i.e previous node) and finally remove the node that is pointed by the head (i.e. previous node). Basically we reverse the arrow between the previous (head) and the next node.

'newHead' is meant to be the last node in the linked list. 'newHead' does not equal the 'next' node. The function keeps returning 'newHead' from each recursive call until it's returned to the original caller.