An easy leetcode question

Python Help
1

Leetcode question 237, delete a node in a linked list, an easy question
It is said to be an easy question. What bothers me is that I do not know how to implement it on my own computer. I need a full example. Moreover, Leetcode provides a list, not a linked list. Do I have to write my own linked list?

This is from the original question:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

I do not have the solution even as a premium member, and this is a widely accepted solution I found on the web:

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

Could anyone provide me with a full example that I can run on my own computer? Do I need a data structure LinkedList along with ListNode? Thank you very much!
What follows is an incomplete solution…


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

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

# How should I initialize a solution class?
# mysol = Solution(...)??
## How should I create a list like the original question?
# 

e1 = ListNode(4)
e2 = ListNode(5)
e3 = ListNode(1)
e4 = ListNode(9)
e1.next = e2
e2.next = e3
e3.next = e4
2

[…]

Do I need a data structure LinkedList along with ListNode?

No. A linked list is just a bunch of nodes connected to each other.
Normally forwards (with a .next) and sometimes as a doubly linked list
(with .next and .previous).

WRT to your code:

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

class Solution(object):
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """

This is a slightly odd way to do a “delete”. Normally to delete a linked
list node you would need the preceeding reference (eg the previous
ListNode or the reference to the front of the list). Your deleteNode
function modifies the existing node to look like the next node,
whereas one might normally expect it to remove the node from the list.
Also, your code does not work for the last node in the list. Try calling
it with e4, for example.

## How should I create a list like the original question?
e1 = ListNode(4)
e2 = ListNode(5)
e3 = ListNode(1)
e4 = ListNode(9)
e1.next = e2
e2.next = e3
e3.next = e4

This is as good a method as any. An alternative method might be to give
a ListNode an “add” method:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
    def add(self, x2):
        node2 = ListNode(x2)
        node2.next = self.next
        self.next = node2
        return node2

which would make a new node and splice it into the list at this point,
so you could go:

e1 = ListNode(4)
e2 = e1.add(5)
e3 = e2.add(1)
e4 = e3.add(9)

which is shorter.

Cheers,
Cameron Simpson cs@cskk.id.au

1 Like