I've written a recursive function to reverse a linked list in Leetcode, but I keep getting just the last node as the result. Here's my code for reference:
```python
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
curr = head
temp = head.next
if temp == None:
return head
return self.reverseList(head.next)
temp.next = curr
curr = temp
```
What am I missing here? Why isn't it working as intended?
3 Answers
You've got some dead code after your return statement. It's best practice to ensure that you're not modifying the input list directly. Instead of trying to reverse the nodes in place with recursion, which can be harder to follow, you might consider returning a new list instead. Generally, a flat loop can be easier to debug and avoids potential stack overflow issues with deep recursion. Leetcode sometimes rewards clever tricks, but clarity is usually more important in production code!
How would I actually implement returning a new linked list instead?
It looks like you've missed understanding how return statements work in functions. They end the function immediately, so anything after the return won't run. Your focus should be on the recursive calls and ensuring proper node connections as the recursion unwinds. It often helps to visualize the linked list and break down your solution step-by-step. Maybe draw it out to get a clearer picture of how your nodes interact throughout the reversal process.
The issue stems from the return statement in your code. When you call `return self.reverseList(head.next)`, it's exiting the function early, leaving any code after that unreachable. As a result, your `curr` variable never gets updated properly, and the reversing logic doesn't execute at all. You essentially have a function that's just going straight to the last node without actually constructing the reverse list.
I totally agree! Leetcode can emphasize quirky solutions, but in real life, clarity and maintainability should take precedence over trying to save a few extra cycles.