The short answer to this is that, Python is a pass-by-object-reference language, not pass-by-reference as implied in the question. It means that:

  1. result and result_tail are two variables that happen to point at the same value
  2. Mutation / Changing of the underlying value (result_tail.next = ListNode(1)) will affect the value shown by result
  3. However, assigning / pointing the variable result_tail to another value will NOT affect the value of result
  4. result_tail = result_tail.next is assigning the next node of the node that is currently assigned by the variable

The following is an visualization of the values that are assigned to the variables (r = result, rt = result_tail):

result = ListNode(0)
#r
#0 -> None

result_tail = result
#r
#0 -> None
#rt

result_tail.next = ListNode(1)
#r
#0 -> 1 -> None
#rt

result_tail = result_tail.next
#r
#0 -> 1 -> None
#     rt

result_tail.next = ListNode(2)
#r
#0 -> 1 -> 2 -> None
#     rt

result_tail = result_tail.next
#r
#0 -> 1 -> 2 -> None
#          rt

References for additional reading:

  • An article explaining the Python pass-by-object reference style in detail https://robertheaton.com/2014/02/09/pythons-pass-by-object-reference-as-explained-by-philip-k-dick/
  • An answer explaining Python's pass-by-object reference style https://stackoverflow.com/a/33066581/12295149
  • Question asking on Python's object reference style Understanding Python's call-by-object style of passing function arguments
Answer from Joseph on Stack Overflow
Top answer
1 of 4
27

The short answer to this is that, Python is a pass-by-object-reference language, not pass-by-reference as implied in the question. It means that:

  1. result and result_tail are two variables that happen to point at the same value
  2. Mutation / Changing of the underlying value (result_tail.next = ListNode(1)) will affect the value shown by result
  3. However, assigning / pointing the variable result_tail to another value will NOT affect the value of result
  4. result_tail = result_tail.next is assigning the next node of the node that is currently assigned by the variable

The following is an visualization of the values that are assigned to the variables (r = result, rt = result_tail):

result = ListNode(0)
#r
#0 -> None

result_tail = result
#r
#0 -> None
#rt

result_tail.next = ListNode(1)
#r
#0 -> 1 -> None
#rt

result_tail = result_tail.next
#r
#0 -> 1 -> None
#     rt

result_tail.next = ListNode(2)
#r
#0 -> 1 -> 2 -> None
#     rt

result_tail = result_tail.next
#r
#0 -> 1 -> 2 -> None
#          rt

References for additional reading:

  • An article explaining the Python pass-by-object reference style in detail https://robertheaton.com/2014/02/09/pythons-pass-by-object-reference-as-explained-by-philip-k-dick/
  • An answer explaining Python's pass-by-object reference style https://stackoverflow.com/a/33066581/12295149
  • Question asking on Python's object reference style Understanding Python's call-by-object style of passing function arguments
2 of 4
16

For those reading this in the future: I wanted to debug linked list problems on a local environment so here is what I did.

  1. Modified the Leetcode code for ListNode by including the dunder "repr" method. This is for when you want to print a ListNode to see what its value and next node(s).
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __repr__(self):
        return "ListNode(val=" + str(self.val) + ", next={" + str(self.next) + "})"
  1. Next, I made a recursive function that makes a nested ListNode when you pass in a list. This is so you can test your methods by passing in lists (instead of having to manually make a confusing looking ListNode yourself.
def list_to_LL(arr):
    if len(arr) < 1:
        return None

    if len(arr) == 1:
        return ListNode(arr[0])
    return ListNode(arr[0], next=list_to_LL(arr[1:]))
  1. Here is an example that tests my answer for the "reverseList" problem:
def reverseList(head: ListNode) -> ListNode:
    prev = None
    while head:
        next_node = head.next
        head.next = prev
        prev = head
        head = next_node

    return prev


# test cases
t1 = list_to_LL([1, 2, 3, 4, 5])  #ListNode(val=1, next={ListNode(val=2, next={ListNode(val=3, next={ListNode(val=4, next={ListNode(val=5, next={None})})})})})
t2 = list_to_LL([1, 2])  #ListNode(val=1, next={ListNode(val=2, next={None})})
t3 = list_to_LL([])

# answers
print(reverseList(t1))
print(reverseList(t2))
print(reverseList(t3))
Discussions

python - How to convert ListNode from LeetCode to regular list? - Stack Overflow
Trying to solve LeetCode "Add Two Numbers". You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes More on stackoverflow.com
🌐 stackoverflow.com
How to create my own input for Python linked list questions? - Stack Overflow
I have just started learning Python through LeetCode. I am in question 876 "Middle of the Linked List". The solution is as below: # Definition for singly-linked list. # class ListNode(obj... More on stackoverflow.com
🌐 stackoverflow.com
How to understand the data structure of Python Linked List in Leetcode - Stack Overflow
I am really confused by the Python linked list data structure used in Leetcode. I am not sure if the problem is caused by the specific ListNode structure created by Leetcode, or I have some More on stackoverflow.com
🌐 stackoverflow.com
Learning python in-depth as new interview language -- what is this "Optional [ListNode]"?
Sorry if stupid question, but Ik alot high level about DSA as I used to do a lot of these problems in C/C++, but now learning about using python as my interviewing lang, i'm confused why the LinkedList is given to me as an "Optional list of Listnodes"? What is the optional part? Why is a linkedList implemented just as a python list? don't i need to traverse it using pointers of some sort? More on reddit.com
🌐 r/leetcode
8
14
October 4, 2022
🌐
LeetCode
leetcode.com › discuss › general-discussion › 388183 › improving-listnode-definition-for-python-problems
Improving ListNode definition for python problems - Discuss - LeetCode
Improving ListNode definition for python problems · Evan Pu · 297 · Array · This definition initialise a listnode without a next value, it is very clunky to use in recursion · class ListNode: def __init__(self, x): self.val = x self.next = None · I think the following init function is much more friendly ·
🌐
LeetCode
leetcode.com › problems › add-two-numbers › discuss › 174970 › Help-with-ListNode-(Python)
Help with ListNode (Python) - Add Two Numbers
Can you solve this real interview question? Add Two Numbers - You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit.
🌐
GitHub
github.com › mcclee › Leetcode-python-Listnode
GitHub - mcclee/Leetcode-python-Listnode: A python class to convert list to Listnode · GitHub
A python class to convert list to Listnode Usage: from ListToListnode import FuckListnode list1 = [1, 2, 3, 4] f = FuckListnode() listnode = f.returnNode(list1)
Author: mcclee
🌐
GitHub
github.com › lyfu19 › Leetcode-Py › blob › main › ListNode.py
Leetcode-Py/ListNode.py at main · lyfu19/Leetcode-Py
class ListNode: def __init__(self, x): self.val = x · self.next:Optional[ListNode] = None · · @staticmethod · def createListNode(nums, pos): """ 根据数组和 pos 创建 ListNode。 · · 参数: - nums: 输入数组,表示链表节点的值。 ·
Author: lyfu19
Find elsewhere
🌐
LeetCode
leetcode.com › problems › add-two-numbers › solutions › 1264577 › python-solution-by-create-a-new-listnode
Python Solution (by Create a New ListNode) - Add Two ...
June 11, 2021 - Can you solve this real interview question? Add Two Numbers - You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit.
🌐
LeetCode
leetcode.com › problems › reverse-linked-list › solutions › 172785 › Python-simple-code-by-using-ListNode-class-definition-(OOP-style).
Python simple code by using ListNode class definition ...
September 21, 2018 - Can you solve this real interview question? Reverse Linked List - Given the head of a singly linked list, reverse the list, and return the reversed list. Example 1: [https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg] Input: head = [1,2,3,4,5] Output: [5,4,3,2,1] Example 2: [https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg] Input: head = [1,2] Output: [2,1] Example 3: Input: head = [] Output: [] Constraints: * The number of nodes in the list is the range [0, 5000]. * -5000
Top answer
1 of 3
1

You need two functions:

  1. One to turn a standard list into a linked list (for calling the middleNode)
  2. One to turn a linked list back into a list (for printing the result)

I would suggest to add methods to the ListNode class. The second one could actually be __iter__ so that a linked list becomes iterable, and then you just have to put the * operator in your print statement:

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

    @classmethod
    def of(Cls, lst):
        head = None
        for val in reversed(lst):
            head = Cls(val, head)
        return head

    def __iter__(self):
        head = self
        while head:
            yield head.val
            head = head.next

class Solution(object):
    def middleNode(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow


head = ListNode.of([1,2,3,4,5])
print(*Solution().middleNode(head))
2 of 3
1

LeetCode lets you specify a linked list using Python list notation for convenience, since you can execute custom unit tests in the browser. The function doesn't actually take in a linked list; if you're running stuff locally, you have to convert from a vanilla Python list to a linked list.

The conversion you've done isn't quite right: what you've done is created a new ListNode that has its val field set to the list [1, 2, 3, 4, 5], and its next field set to None.

Here's what you're looking for (iterating over each element in the input list, and inserting them into a linked list):

def convert_to_linked_list(input_list):
    head = None
    for i in range(len(input_list) - 1, -1, -1):
        new_head = ListNode(input_list[i], head)
        head = new_head
    return head

Edit: To print out the values in the linked list (as asked in a follow-up):

ll = convert_to_linked_list([1, 2, 3, 4])
current = ll
while current is not None:
   print(current.val)
   current = current.next
🌐
Reddit
reddit.com › r/leetcode › learning python in-depth as new interview language -- what is this "optional [listnode]"?
r/leetcode on Reddit: Learning python in-depth as new interview language -- what is this "Optional [ListNode]"?
October 4, 2022 - So Optional[ListNode] means that either the return value is of type ListNode, or potentially None which in this case would be if your linked list is empty (hence head is also potentially None or a ListNode type).
🌐
Reddit
reddit.com › r/learnprogramming › help me understand the listnode structure from leetcode [c++]
r/learnprogramming on Reddit: Help me understand the ListNode structure from LeetCode [C++]
December 22, 2020 -

I know it's a dumb question, but I would like to know how the structure works and what does each line does / works. Also, when solving problems from LeetCode I like to write and test the code on my own machine, so I would also like to know how to create one of those structures with my own values.

Here's the structure that is shown in LeetCode:

struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
};

Also, here's a link to the problem in case it helps.

Thanks in advanced.

Top answer
1 of 2
2
A listNode holds an integer and a pointer to another listNode. Since each node can hold a reference to the next node and that node can hold a reference to the next node, and so on, it allows you to create a list that can be added to and removed from dynamically as needed. The three constructors allow you to specify no parameters (the node defaults to holding 0 and null) just the int parameter, or both the value and next parameters.
2 of 2
1
I am going to explain it, but realize that if you have never even worked with linked lists before it will be pretty hard to solve leetcode problems using them. I would recommend learning about linked lists first, this video seems pretty good : https://www.youtube.com/watch?v=WwfhLC16bis . That ListNode structure contains 5 things : an int so that the node can store data, a pointer which can be used to connect this node to another one (called next in this case), and 3 different constructors. You can spot a constructor in most languages because it has the same name than the class/struct it's in (at least for C++ and Java). It's just a function that allows you to actually build that object when you need to later. There are 3 different versions here to allow you to build a ListNode with its value and pointer already determined, or not depending on what you need. To populate a linked list the lazy way, I recommend starting from the end. Say you want a list such as 1->2->3, you first create a node which contains 3 and doesn't point anywhere. Then you create a node which contains 2 and points to the node we just made. Then you make a node which contains 1 and points to the previous one. Now the node that contains 1 is the "head" of your linked list. But since you are learning linked list for the first time, I highly recommend making a function to create the linked list for you instead from an array, because you will learn more by doing this, and it will allow you to then create lists much more quickly if you want to test different things out. Such a function could look like this : ListNode createLinkedList( *insert array here* ) { *your code here* } and you would call it by making an int array and passing it as an argument like this : int coolArray[3] = { 1, 2, 3 }; ListNode quickAssNode = createLinkedList( coolArray);
🌐
Python.org
discuss.python.org › python help
An easy leetcode question - Python Help - Discussions on Python.org
February 23, 2022 - 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 soluti...
🌐
GitConnected
levelup.gitconnected.com › python-unleashed-cracking-the-leetcode-100-linked-list-part-iii-42023bdf58c1
Python Unleashed: Cracking the LeetCode 100 — Linked List-Part: III | by Senthil E | Level Up Coding
July 30, 2023 - ListNode(x): This is how we create a new node with value x for a linked list in Python. Leetcode problem number: 146 Difficulty level: Medium
🌐
LeetCode
leetcode.com › problems › merge-k-sorted-lists › discuss › 265225 › easy-python-heapq-with-listnode-in-leetcode-environment
Easy Python heapq with ListNode in LeetCode environment
March 30, 2019 - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
🌐
Physics Forums
physicsforums.com › other sciences › programming and computer science
Python header question from leetcode solution • Physics Forums
January 28, 2022 - Bear in mind that creating the input list is not part of the LeetCode challenge which you can see here: https://leetcode.com/problems/remove-nth-node-from-end-of-list/ - you need to select Python3 from the dropdown manually. Jan 28, 2022 · #10 · pbuk · Science Advisor · Homework Helper · Gold Member · 5,012 · 3,255 · Mark44 said: I thought about how this might be done using just one loop, starting from the end node. Nothing came immediately to mind, though. Python: items = [1, 2, 3, 4, 5] head = None for value in reversed(items): head = ListNode(value, head) Python How to build a linked list in python ·
🌐
AlgoMonster
algo.monster › home › 203. remove linked list elements
203. Remove Linked List Elements - In-Depth Explanation
Python · Java · C++ TypeScript · Copy · 1# Definition for singly-linked list. 2# class ListNode: 3# def __init__(self, val=0, next=None): 4# self.val = val 5# self.next = next 6 7class Solution: 8 def removeElements(self, head: ListNode, val: int) -> ListNode: 9 # Create a dummy node pointing to the head 10 # This handles the edge case where the head itself needs to be removed 11 dummy_node = ListNode(-1, head) 12 13 # Initialize pointer to traverse the list 14 # Starting from dummy node ensures we can modify the head if needed 15 previous = dummy_node 16 17 # Traverse the list until we re
🌐
LeetCode
leetcode.com › problems › add-two-numbers › solutions › 749878 › how-do-i-use-listnode-in-this-problem-python
Add Two Numbers - LeetCode
July 22, 2020 - Can you solve this real interview question? Add Two Numbers - You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit.