LeetCode with Corgis and Kittens — Visual Guide in Solving the Add Two Numbers Problem !!!

LeetCode with Corgis Comic GIF🎁 Issue #2 — Visual guide in solving the Add Two Numbers Problem

Hello 👋💻🌎 Tech World,

LeetCode with Corgis and Kittens Problem #2— Add Two Numbers

MAKING LEARNING HOW TO CODE

✧・ﾟ:* CUTE(◕‿◕✿) and INFORMATIVEᕙ(⇀‸↼‶)ᕗ!!!

Hope you enjoy it!

codewithcorgis/LeetCode-With-Corgis

Problem Statement

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. Add the two numbers and return them 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.

Add Two Numbers Animation

Figure 1. Visualization of the addition of two numbers: 342+ 465 = 807.
Each node contains a single digit and the digits are stored in reverse order.

Algorithm

Just like on a piece of paper📄, sum two numbers we start to begin by summing the least-significant digits, which is the head of l1 (linked list 1 ) and l2 (linked list 2). Since each digit is in the range of 0…9, summing two digits may “overflow”. For example 5 + 7 = 12. In this case, we set the current digit to 2 and bring over the carry = 1 to the next iteration. carry variable must be either 0 or 1 because the largest possible sum of two digits (including the carry) is 9+9+1=19.

The pseudocode (recipe guide) is as follows:

• Initialize the current node to dummy head of the returning list.
• Initialize carry to 0.
• Initialize p and q to head of l1 and l2 respectively.
• Loop through lists l1 and l2 until you reach both ends.

1. Set x to node p’s value. If p has reached the end of l1, set to 0
2. Set y to node q’s value. If q has reached the end of l2, set to 0.
3. Set sum = x + y + carry.
4. Update carry = sum/10.
5. Create a new node with the digit value of (sum mod 10) and set it to the current node’s next, then advance the current node to next.
6. Advance both p and q.

• Check if carry=1, if so append a new node with digit 11 to the returning list.
• Return dummy head’s next node.

Note: that we use a dummy head to simplify the code. Without a dummy head, you would have to write extra conditional statements to initialize the head’s value.

Take extra caution of the following cases:

The sum could have an extra carry of one at the end, which is easy to forget.

Follow up

What if the digits in the linked list are stored in a non-reversed order? For example:

(3→4→2) + (4→6→5) = 8→0→7

Approach 1: Elementary Math ➕

Java☕

JavaScript💛🍦

Python 🐍

Complexity Analysis

• Time complexity ⏰ : O(max(m,n)) Assume that m and n represent the length of l1 and l2 respectively, the algorithm above iterates at most max(m,n) times.

• Space complexity🚀 : O(max(m,n)) The length of the new list is at most max(m,n)+1.

Please clap if it helps … Thank you for reading ❤ ,

Kodie The Coding Corgi & Bits The A.I.

codewithcorgis/LeetCode-With-Corgis

P.S. If this comic strip was able to help you in any way, sign up for our newsletter it means a lot and to send your thoughts and feelings about this work. DM us on Instagram or tweet us on Twitter. Please share this with your coding friends, corgis friends, and coding corgis friends so we can make more comics in the future with your support. Thank You!