Why is the output an empty list, when I call a function that skips nodes in a linked-list?

Question

I am writing code to answer the following LeetCode question:

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head

Example 1
Input: head = [1,2,6,3,4,5,6]
       val = 6 
Output: [1,2,3,4,5]

This is my code:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        curr= head
        dummy=ListNode(0)
        prev=dummy

        def skipper(prev,curr):  
            if curr.val == val:
                curr = curr.next
            else:
                prev.next = curr
                temp = curr
                prev = temp
                curr = curr.next

            while prev.next:
                if prev.next.val == val:
                    prev.next = curr
            return curr

        while curr: 
            return skipper(prev,curr)


        return dummy.next

For the above code, I know that the logic works, because when I replace the inner function def skipper(prev,curr) with just while curr, and remove the while curr at the bottom of the code, then the code passes all tests.

But I want to understand how to use/call a function within a function.

The skipper function is simply meant to run through the linked list one node at a time, and 'remove' or relink the nodes so as to skip any nodes that have the same value as val.

My issue is I am not sure what to return inside the skipper function, and as a default I have returned curr- since to me this makes some sense.

But when I run the above code, I get a timeout error.

don't use "next" as identifier, it is a python function. What is "dummy"? How do you run this code? — Yuri
– Yuri, Commented Jun 15, 2021 at 8:40
Thanks Sayse- I have added a return curr now. But the output still isn't quite right. But when I run it on paper it should give the correct result. — hefu fhiwh
– hefu fhiwh, Commented Jun 15, 2021 at 8:52
I think I just realised the mistake- I am doing prev=curr then changing curr in the next line! — hefu fhiwh
– hefu fhiwh, Commented Jun 15, 2021 at 9:20

trincot · Accepted Answer · 2021-06-15 10:52:55Z

1

Some issues in your code (as it was first posted):

return skipper(prev,curr) is going to exit the loop, but there might be more nodes to be removed further down the list. skipper only takes care of a sub sequence consisting of the same value, but it will not look beyond that. The list is not necessarily sorted, so the occurrences of the value are not necessarily grouped together.
Be aware that the variable prev in skipper is not the same variable as the other, outer prev. So the assignment prev=curr in skipper is quite useless
Unless the list starts with the searched value, dummy.next will always remain None, which is what the function returns. You should initialise dummy so it links to head as its next node. In your updated code you took care of this, but it is done in an obscure way (in the else part). dummy should just be initialised as the head of the whole list, so it is like any other node.

In your updated code, there some other problems as well:

while prev.next: risks to be an infinite loop, because it continues while prev is not the very last node, but it also doesn't move forward in that list if its value is not equal to the searched value.

I would suggest doing this without the skipper function. Your main loop can just deal with the cases where current.val == val, one by one.

Here is the corrected code:

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        curr = head
        dummy = ListNode(0, head)  # Link to head!
        prev = dummy

        while curr: 
            if curr.val == val:    
                prev.next = curr.next  # This is all that needs to happen
            else: 
                prev = curr
            curr = curr.next  # This should happen in both cases
            # The loop invariant is: prev.next == curr

        return dummy.next

I don't see a benefit in having a separate skipper function, as in the end it will have to do all that the main function will have to do: i.e. find the occurrences of val and skip them.

If you really want a sub function, then maybe do:

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        curr = head
        dummy = ListNode(0, head)
        prev = dummy

        def skipper(curr):
            while curr is not None and curr.val == val:
                curr = curr.next
            return curr
        
        while curr: 
            if curr.val == val:    
                prev.next = skipper(curr)
            else: 
                prev = curr
            curr = prev.next

        return dummy.next

edited Jun 15, 2021 at 10:52

answered Jun 15, 2021 at 10:37

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

hefu fhiwh Over a year ago

thanks again trincot for the explanation, I understand now. A quick question about reassigning variables: I can see an issue with doing prev=curr then curr=curr.next right after; as prev points to curr, which we are changing straight away! Someone suggested the solution temp=curr, prev=temp then curr=curr.next; and in this way prev doesn't get reassigned to curr.next. But I don't see how this is the case, because when you do curr=curr.next; this changes curr, and so won't this also change temp and prev as a result??

trincot Over a year ago

No, prev=curr; curr=curr.next is not a problem. The second assignment will have no effect on prev. It is a different thing, when you mutate an object, like if after those assignments I would do prev.next.val = 10, then I will have modified the object that also curr is referring to, so what ever happens to prev.next.val happens to curr.val and vice versa, as prev.next and curr reference the same object. But assigning to a variable, will never impact anything else than that variable.

hefu fhiwh Over a year ago

Hi Trincot, I was just going through your above code with the sub function. And I wanted to confirm something- the skipper function returns curr; so does this curr then take the place of "skipper(curr)" in the line prev.next=skipper(curr)

Collectives™ on Stack Overflow

Why is the output an empty list, when I call a function that skips nodes in a linked-list?

Example 1

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Example 1

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related