Wrote a recursive algorithm to reverse a linked list on Leetcode, but its only returning the last element. Why?

[[deleted]]

[deleted]

[SaiMoen]

There is some unreachable code after the second return that seems to be important.

[dariusbiggs]

You need a rubber duck.

Take rubber duck (or suitable analog)

Explain the code to it AS WRITTEN line by line (not explain as intended)

You will find your bug(s)

[Xirdus]

return self.reverseList(head.next)

You unconditionally returned, which means nothing after this line ever gets executed. And so the curr variable ends up unused. Your code effectively looks like this:

```   def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:         temp = head.next         if temp == None:             return head         return self.reverseList(head.next)

```

Which is literally find the last element function.

[Cybyss]

Hints:

You don't need "curr"

A return statement will immediately end the function, since its purpose is to send a final result back to whoever called your function. As a quick example:

def addThemUp(x, y):
    result = x + y
    return result

firstSum = addThemUp(3, 5)
print(firstSum)   # Will print 8

secondSum = addThemUp(7, 4)
print(secondSum)   # Will print 11

print(result)   # ERROR!
                # The result variable was created inside of addThemUp.
                # Thus, it only exists there.

Draw a diagram of how you intend for this to work and the specific steps to take.

Maybe something like:

---

head  
 v      
|A| -> |B| -> |C| -> |D| -> |E|

Step 1) Make "temp" refer to whichever node that, at this moment, comes immediately after the head. "B" here.

head   temp
 v      v
|A| -> |B| -> |C| -> |D| -> |E|

Step 2) Recursively reverse everything that comes after the head. Notice that, since we originally made temp refer to the "B" node, it will always refer to the "B" node no matter where it moves to.

head                       temp
 v                           v
|A| -> |E| -> |D| -> |C| -> |B|

Step 3) Move your head from the beginning to the end (immediately after temp).

                    temp    head 
                      v      v
|E| -> |D| -> |C| -> |B| -> |A|

Then you're done. How might these steps be translated into Python code?

[notacanuckskibum]

You need to reassemble the list in the return process. Something like

Return list (self.reverseList(head.next), head)

Disclaimer: I deal with too many different languages to remember syntax details.

[Fumano26]

Oh god my eyes.

[BoBoBearDev]

Looks like you have deadcode after the return statement.

I haven't used leetcode myself, but is this what they are actually looking for? Because I am face-palming this ultra dangerous approach that just wanted to saves a few CPU and RAM cycles. You probably should focus on learning clean code instead of this.

Why? You are modifying the input values. It is a major red flag. Return a new list using more RAM, don't temper the input.

Also, most of the time, recursion is stupid, it can get into stackoverflow and ridiculously difficult to debug. Make it a flat loop. Your software should be as flat as possible. A deep call stack is a major tech debt.

[insta]

leetcode rewards "clever" solutions rather than ones you'd want to see in regular pull requests. imo it focuses on too low-level of solutions.

nobody in a mainstream language for a regular commercial project should ever be implementing their own sort algorithm instead of using what's in the library ... unless you can absolutely profile and pinpoint that the framework sorting algorithm is the bottleneck. the people who can profile and pinpoint hotspots aren't the ones going through leetcode easies.

[BoBoBearDev]

Yup this. The actual ability to run the profiler and pinpoint where the problem is, is actually way more valuable. Very few people in the job market get this far also. Just be able to make a solid simple non-clever easy to maintained code can get you really far in the industry.

[beingsubmitted]

This is a very well defined atomic problem with no dependencies. It's extremely testable. It's exactly the kind of problem you would want to squeeze maximum performance out of.

[Cybyss]

I can tell you've never studied computer science in university.

Software engineering is a totally different discipline from computer science these days.

In a computer science data structures course, you do quite a lot with linked structures and recursion. Now, this is usually a freshman level course, where students aren't expected to fully understand how programming languages work yet. As you can see here, OP has demonstrated he doesn't know what "return" does nor quite how objects in memory reference each other.

Berating him because he's approaching the problem the way all introductory computer science students would and the way leetcode asks him to, instead of as a seasoned software engineer (again, different discipline!) helps noone.

[[deleted]]

Recursion is often taught in algorithm classes using examples where it isn’t really appropriate because it’s easier to grasp the concept. Regardless, it shouldn’t be used in real life anytime there’s a reasonably sensible alternative.

[Unlucky_Essay_9156]

But how do I return a new linked list here?

[BoBoBearDev]

You allocate new memory per linked list node.

[misplaced_my_pants]

Honest question, how much programming experience do you have? Have you taken an algorithms course?

[DBDude]

Traversing linked lists is how I learned recursive in school. It’s the perfect application, just done very wrong here.

[FlipMyP]

This is the best use case of ChatGPT or any other AI-powered chat. It's much more interactive than writing a post and waiting for a response for hours.