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
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 inplace instead.
"""
while node.next:
node.val = node.next.val
node = node.next
node = None
deleteNode(node4)
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
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 inplace 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