Recursively Reverse a Linked List
The recursive version of this problem is slightly trickier and the key is to work backwards. Assume that the rest of the list had already been reversed by Recursion, now how do I reverse the front part? Let’s assume the list is:
n1 → … → nk-1 → nk → nk+1 → … → nm → Ø
Assume from node nk+1 to nm had been reversed and you are at node nk.
n1 → … → nk-1 → nk → nk+1 ← … ← nm
We want nk+1’s next node to point to nk.
So, nk.next.next = nk;
Be very careful that n1’s next must point to Ø. If you forget about this, your linked list has a cycle in it. This bug could be caught if you test your code with a linked list of size 2.
INTUITION:
Assume that we have a linked list [1,2,3,4,5,6,7] and our Recursion had already reversed the list from 4 to 7 i.e current scenario is [1,2,3,7,6,5,4] now we have to find out a way to add 3 to the reversed list.
Think why head is pointing at 3 !!
def reverseList(self, head):
if not head or not head.next:
return headreversed_list = self.reverseList(head.next)
head.next.next = head
head.next = Nonereturn reversed_list
Please refer this link for practice https://leetcode.com/problems/reverse-linked-list/
Thank You !! Happy Coding
