o-o o-o - 3 months ago 13
Python Question

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

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.

Answer

You were almost there, but are doing way too much work shifting all val values up one node. You also forgot to clear the last next reference, which is why you see 5 printed twice.

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.

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 'last' node reference and clear the .next attribute on that once looping is done:

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

# clear reference to tail
prev.next = None
Comments