Meet again in the episode of I re-learn something that I don’t applied in my daily work task. Yeah, just want to learn it again and I hope this time I get the most of the understanding. I will push myself for this three months to re-learn DSA, before I get into the new job. Just wanna straight away write what I just realize during my attempt to solve the easy (said by Leetcode) problem which is Add Two Numbers.

Linked List

Fundamental

This problem require an understanding to the concept of Linked List. To be honest, I have watched some videos and read some articles on the internet but still failed to grasp the main concept of it. I guess I need to face the problem first then my brain can work 100% efficiently.

So, what I realized, the first thing you need to put in your mind while learning about Linked List is

To remove the concept of common list that I understand, which a list that can be access by indices (index).

Why? Because I realized the blockade that prevent me to understand the concept of linked list. The main concept of Linked List is the

1. Node

2. Pointer

Only this, then the manipulation of memory allocation. Reading the theory personally make me feels dizzy, so I straight away going to the code. The problem is, how do they thought on the way to create the Linked List is in this way?

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

Remember that, if you instantiate an object from a class, it will allocate the object (which variable also one of it) into the memory.

Hence, to utilize this feature, they write a single Node as an object in the variable.

From the code you can see there is 2 object attributes (val and next) which represents

1. val — value that we want to store in the node

2. next — an attribute that we use to manipulate the state of pointer

By using this Class, we can create a Linked List and store the value in it. Let’s do some simple proves. To create a linked list, we use this function;

def list_to_linked_list(lst):
    dummy = ListNode() # first node
    temp = dummy

    # for every, initially create new node, then create new node
    # after it
    for val in lst:
        temp.next = ListNode(val)
        temp = temp.next
    return dummy.next # in the end it point to the head of the ll

Pseudocode:

1. We first instantiate the first node with dummy

2. Then we copy the object to temp

3. For every integer in the list, I will assign the .next value from temp a node with the integer value.

4. Then I will overwrite the temp with temp.next for the next iteration.

5. The next iteration, we actually create a node for temp.next.next.

6. Until the iteration end.

7. Then we point the pointer to the first node, which is dummy

Example:

l1 = list_to_linked_list([1,2,3])

a = l1.next
b = a.next

print(l1.val, a.val, b.val)

#### OUTPUT ######
(1, 2, 3)

This is actually similar to

print(l1.val, l1.next.val, l1.next.next.val)

#### OUTPUT ######
(1, 2, 3)

To visualize this,

Okay that solved the Linked List part, not the problem yet. Honestly, I did not solved the problem, but I learned from the solution.

Solution

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # Dummy node to start the new list
        dummy = ListNode()
        temp = dummy
        carry = 0

        # Loop until both lists are processed or there is a carry
        while l1 or l2 or carry:
            # Get values from the current nodes or use 0 if the node is None
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            # Calculate the sum and the new carry
            # carry - imagine standard written method,
            # where if the the summation is more than 10,
            # it will carry the 1 value to the next side opearation
            total = val1 + val2 + carry
            carry = total // 10
            value = total % 10

            # Create a new node with the current value and move the pointer
            temp.next = ListNode(value)
            temp = temp.next

            # Move to the next nodes in the input lists if they exist
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next

        # Return the head of the new linked list
        return dummy.next

So, based on the code, we can see a similar code structure like the way we create the linked list above.

Common parts;

1. ListNode()

2. dummy

3. temp

4. carry

The extras is before we create the Node and store the value, we do something with the linked list. In this part, we need to imitate the elementary school standard operation procedure in addition, where if the operation of integer is more than 10, then we need to bring the 1 to the next position.

In Leetcode, they use the word traversing which simply means

Iterate until there is no value, or simply said , while True

1. So, traversing into first and second linked list, we take the value and total it up. We check if there is a carry (more than 1 and take the value 1 to the next) and bring keep for the next iteration.

2. We then keep the total addition operation by doing modulo and keep it in a new node, and keep it in temp.

3. The current temp already has value, hence we overwrite it and create a new one.

4. Since l1 and l2 is already a Linked list, we can move to the next node for the next operation.

5. Finally, after the linked list creation complete, we point and skipped the dummy node.

Recap

1. To solve the linked list is to have the linked list mindset in mind (not the common Python list that I learned in the fundamental part).

2. Input linked list, output linked list.

3. Basic structure of linked list to have value and pointer.

4. Manipulate the pointer following to what the problem or stuffs you need to solve.

5. Common manipulation use dummy and temp in order to achieve the objective.