menu

Back To Back SWE

We help software engineers find the job of their dreams with exceptional explanations & teaching resources

Channels
Team

Hey, I didn't understand this recursive solution of reversing a linked list

May 3, 2020 at 7:52pm

Hey, I didn't understand this recursive solution of reversing a linked list

May 3, 2020 at 7:52pm
class Solution { public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode next1 = reverseList(head.next);
head.next.next = head;
head.next = null;
return next1;
}
} // Why did we write those lines: // head.next.next = head; //head.next = null;
// Please advise

May 4, 2020 at 2:40pm
head.next.next = head;: Imagine it like this (head.next).next, we are pointing the next pointer of head.next (which is the node currently after head, remember we are going up in the recursion at this point) to head which is the node held by the recursive function call. This reverses head.next's link.
head.next = null;: We cut off the next pointer of head because it may be the last node in the linked list and it is still pointing to head.next.
Consistently consider what this looks like in memory. Use the (head.next).next parentheses technique to narrow down what in memory is being manipulated. This is useful when considering functional problem approaches (where we pass functions and use functions to birth functions, etc.).
Edited
like-fill
3
  • reply
  • like

May 9, 2020 at 11:10am
Thank you so much for your great explanation. I also watched your video explanation on Youtube: https://www.youtube.com/embed/O0By4Zq0OFc It's really really a great video explanation. I've never seen another person who explained recursion that way.
Edited
  • reply
  • like

May 10, 2020 at 10:11am
glad it helps.
  • reply
  • like