Trying to figure out how to reference Listnodes in a coding challenge

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 contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

My main confusion here is that I’m not sure how to reference numbers from a linked list, as they are not iterable, nor indexable.
Link to real problem: https://leetcode.com/problems/add-two-numbers/

There’s a comment in the default code showing how a node stores its data

2 Likes

You mean like this?:

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

That’s how the type of the nodes is defined, not how you would access the numbers. You won’t need that code unless you’re creating your own nodes for whatever reason.
But it does show you its structure, and if you know its structure then you can pick things out from it.

2 Likes

So there are six total digits, 2 linked lists, each list contains 3 digits. How would one access an individual digit from a list with just self.val? This would only allow you to access one digit per linked list.

no, per node. there’s one digit per node. next digit is in next node.

2 Likes

L1 = (1 -> 2-> 3)

Is this correct?
L1.val = 1
L1.next = 2

I’m not sure how to get to the third digit:

L1.next.next = 3? Probably not

2 Likes

Ok, so L1 and L2 are not references to the linked lists, they are references to individual nodes. I guess my only question is now is how do you reference a particular node if you cant index a linked list?

l2 and l1 are lists.
what is a linked list? nodes. linked. how do you traverse it? follow the links.

1 Like
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

^This says that l1 and l2 are ListNodes.

A node is a list. A list is made from nodes.

1 Like

So a list is a node, the nodes within a list are nodes. So really there are 8 nodes. Both lists and 3 digits per list

The nodes are not in a list. The nodes are the list… Did you watch the video? Go watch the video. Or look up linked list on wikipedia, or anywhere.

Better yet, implement your own linked list, and some operations for it, like insert, append, prepend, filter, map.

1 Like

A list can be empty:

Empty

Or, it can be a node, and that is a value and the rest of the list.

Node 5 Empty

To add a value, create a new node and refer to the rest of the list.

Node 3 (Node 5 (Empty))
Node 1 (Node 3 (Node 5 (Empty)))

…To traverse it,
if it is empty then you are done.
if it is not empty, then look at the value of the node, and then traverse the rest

1 Like

This video explains exactly how linked lists work with a notebook and pen without explaining the code behind it. This I understand. I’m just confused about traversal and the meaning of certain lables like ‘self.val’. Does self.val reference the first node in a list? or the list itself? Self.next reference the next node.

So if I have l1: (1-2-3) and l2: (4-5-6)

What does l1.val reference? 1? Or is there still something fundamental which I am missing?

In the video they show nodes as a box with two variables.
In your code you have a … box with two variables. It’s the same thing, there’s nothing else to it, that is all there is.

print it and find out?

2 Likes

How does traversal work?

So tha value of the node is just the node in front? If next is set to none, then how can you traverse the list?

None is also a valid list, so that case is not different.

2 Likes