Python delete a node in linked list, given just access to that node

Question

This is a LeetCode question, I knew its solution, but wondering about why my code not work.

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function

At first glance, my intution is delete like an array:

shift all the node values one front, then delete the tail, here's my implementation and test case:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
        
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5


    
def deleteNode(node):
    """
    :type node: ListNode
    :rtype: void Do not return anything, modify node in-place instead.
    """
    while node.next:
        node.val = node.next.val
        node = node.next
    node = None
    
    
deleteNode(node4)

But After deletion, it has two 5 value nodes, the tail was still kept, can anyone please explain to me what's wrong here?

deleteNode(node4)

node1.val
Out[162]: 1

node1.next.val
Out[163]: 2

node1.next.next.val
Out[164]: 3

node1.next.next.next.val
Out[165]: 5

node1.next.next.next.next.val
Out[166]: 5

Really appreciate any help.

Martijn Pieters · Accepted Answer · 2016-08-10 18:08:48Z

9

You were almost there, but are doing way too much work shifting all val values up one node. You also failed to clear the last next reference, which is why you see 5 printed twice. I'll show you how to solve the problem properly first, then address removing the tail.

You can indeed solve this puzzle by not deleting the node, just by setting the value to the next value, and the next pointer to the node after the next. And that is all you need to do, you don't need to touch any of the following nodes. You'd effectively delete the next node and making this node hold the next value instead:

      node
       |
       v
      ---------        ---------       
---> | val: va | ---> | val: vb | ---> ?
      ---------        ---------

becomes

      node
       |
       v
      ---------        ---------       
---> | val: vb | -+   | val: vb |   -> ?
      ---------   |    ---------   |   
                  |                |
                   ----------------

So the implementation is as simple as:

def deleteNode(node):
    """
    :type node: ListNode
    :rtype: void Do not return anything, modify node in-place instead.
    """
    node.val = node.next.val
    node.next = node.next.next

No loop required.

Back to your attempt, note that the last line in your function has no effect. node is a local name in your function, and references the tail ListNode instance, until you set it to None instead.

You had this:

      node
       |
       v
      -----------       
---> | val: tail | ---> None 
      -----------

and node = None does this:

      node -> None
       X
       |
       v
      -----------       
---> | val: tail | ---> None 
      -----------

That incoming reference from the previous node is still there.

You'd have to track the 'one-but-last' node reference and clear the .next attribute on that once looping is done:

while node.next:
    node.val = node.next.val
    prev, node = node, node.next

# clear reference to tail
prev.next = None

edited Aug 10, 2016 at 18:08

answered Aug 10, 2016 at 16:53

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

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

3 Comments

xue Over a year ago

yes, you're right, I did a more work than needed, and could you look at my code, I think I did clean the tail, but the tail still there confused me.

Martijn Pieters Over a year ago

@o-o: node = None only sets the local name. The reference in the preceding node is unaffected.

NinjaGaiden Over a year ago

You make it so simple. Great answer

Jacques de Hooge · Accepted Answer · 2016-08-10 16:57:08Z

1

def deleteNode(node):
   node.val = node.next.val
   node.next = node.next.next

Since you don't have a reference to your current node, you can't delete it. But you do have a ref to your next node. So give your current node the role that your next node previously had, and then the garbage collector will delete your next node, since there are no refs to it left because you overwrote node.next.

edited Aug 10, 2016 at 16:57

answered Aug 10, 2016 at 16:54

Jacques de Hooge

7,0002 gold badges33 silver badges48 bronze badges

Collectives™ on Stack Overflow

Python delete a node in linked list, given just access to that node

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related