Add Two Numbers

You can add two numbers represented by two linked lists by simulating the addition from right to left, just like how you do addition on paper. You’ll iterate through both linked lists and keep track of the carry to handle cases where the sum of two digits is 10 or more.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy_head = ListNode(0)
        current = dummy_head
        carry = 0

        # Iterate through both linked lists
        while l1 or l2:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            # Calculate the sum and carry
            total_sum = val1 + val2 + carry
            carry = total_sum // 10
            current_sum = total_sum % 10

            # Add the current sum to the new linked list
            current.next = ListNode(current_sum)
            current = current.next

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

        # If there is a remaining carry, add a new node
        if carry > 0:
            current.next = ListNode(carry)

        return dummy_head.next

This code constructs a new linked list that represents the sum of the numbers in the given linked lists. It handles different lengths and a carry that persists to a new digit at the left end.

Clarification Questions

Node Value Limits: The problem states that node values are between 0 and 9. Is it safe to assume these constraints will always be met?
Null Handling: What should the output be if one or both of the input linked lists are null?
Output Format: Is the output also expected to be in reversed order, similar to the input linked lists?
Memory Constraints: Are there any limitations on the memory usage for solving this problem?
In-Place Modification: Is modifying the input linked lists allowed, or do we need to create a new linked list for the output?
Leading Zeros: The problem states there won’t be leading zeros in the input numbers. Does this apply to the output as well?
Duplicate Nodes: Can the linked list have nodes with the same value next to each other? For example, is [2,2,2] a valid linked list for this problem?
List Length: The problem constraints state the number of nodes is between 1 and 100. Is it guaranteed that this constraint will not be violated?
Time Complexity: Is there a time complexity constraint for solving this problem?
Case Sensitivity: Is the output case-sensitive? For example, should “Yes” and “No” be capitalized?
Result Order: The problem does not specify the order of the result. Is any order acceptable?

Asking these clarification questions can help to better understand the problem’s edge cases, constraints, and requirements.

Identifying Problem Isomorphism

The problem is a classic linked list problem that often goes by the name “Add Two Numbers”. In terms of isomorphism, or a problem that maps closely to the underlying structure of this one, you might consider LeetCode problems that involve number manipulation using linked lists or arrays.

One such problem is “Multiply Strings” (LeetCode #43), where instead of adding numbers, you’re multiplying them, but the process involves breaking down the numbers into their constituent digits and doing operations digit-by-digit, quite like the “Add Two Numbers” problem.

Another example is “Add to Array-Form of Integer” (LeetCode #989), where you’re adding an integer to an array-form number. Although it’s not with linked lists, the digit-by-digit addition and carry-over logic would be similar.

Also, “Plus One” (LeetCode #66) is simpler but has some resemblance in the sense that you’re dealing with digits and possible carry-over situations.

These problems share the underlying concept of manipulating numbers at the digit level, usually involving some kind of carry-over operation which is the core concept in “Add Two Numbers”.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
# @return a ListNode
def addTwoNumbers(self, l1, l2):
    carry = 0
    root = n = ListNode(0)
    while l1 or l2 or carry:
        v1 = v2 = 0
        if l1:
            v1 = l1.val
            l1 = l1.next
        if l2:
            v2 = l2.val
            l2 = l2.next
        carry, val = divmod(v1+v2+carry, 10)
        n.next = ListNode(val)
        n = n.next
    return root.next

Language Agnostic Coding Drills

Step 1: Understanding Classes and Objects A class is a blueprint for creating objects, and an object is an instance of a class. A class can contain properties and methods.

Drill: Create a simple class with one property and one method.

Step 2: Understanding Linked Lists A linked list is a linear data structure where each element is a separate object, called a node. Each node contains a value and a reference (link) to the next node in the sequence.

Drill: Implement a singly linked list with methods to add and remove nodes.

Step 3: Understanding Iteration through Linked Lists One can traverse through a linked list by continuously moving to the next node until the end of the list (represented by a null reference).

Drill: Write a function that iterates over a linked list and prints out the value of each node.

Step 4: Understanding Basic Arithmetic The code involves simple addition and carry-over operations, similar to what is done in primary school arithmetic.

Drill: Write a function that adds two large numbers represented as strings.

Step 5: Understanding the ‘divmod’ function The built-in ‘divmod’ function takes two numbers and returns a pair of their quotient and remainder.

Drill: Write a program that takes two integers and prints their quotient and remainder without using the ‘divmod’ function.

Step 6: Combining the concepts This step involves writing a function similar to the addTwoNumbers method that takes two linked lists representing numbers and returns a new linked list representing their sum.

Drill: Write a function that takes two linked lists, where each node contains a single digit, and returns a new linked list representing the sum of the two input lists.

Targeted Drills in Python

Drill 1: Understanding Classes and Objects

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# Create a simple class called 'Person' with a property 'name' and a method 'say_hello' 
# that prints out a greeting.

class Person:
    def __init__(self, name):
        self.name = name

    def say_hello(self):
        print(f"Hello, my name is {self.name}!")

# Create an object of the class and call the method
p = Person("Alice")
p.say_hello()

Drill 2: Understanding Linked Lists

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Define a class for a Node and a Linked List

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def add_node(self, data):
        if not self.head:
            self.head = Node(data)
        else:
            cur_node = self.head
            while cur_node.next:
                cur_node = cur_node.next
            cur_node.next = Node(data)

    def print_list(self):
        cur_node = self.head
        while cur_node:
            print(cur_node.data)
            cur_node = cur_node.next

# Create a linked list and add nodes
ll = LinkedList()
ll.add_node(1)
ll.add_node(2)
ll.add_node(3)

ll.print_list()

Drill 3: Understanding Iteration through Linked Lists

1
2
3
# Using the LinkedList class from the previous drill, iterate over the linked list and print each value.

ll.print_list()

Drill 4: Understanding Basic Arithmetic

1
2
3
4
5
6
# Write a function to add two large numbers represented as strings

def add_large_nums(num1, num2):
    return str(int(num1) + int(num2))

print(add_large_nums("123456789123456789", "987654321987654321"))

Drill 5: Understanding the ‘divmod’ function

1
2
3
4
5
6
7
8
# Write a function to print the quotient and remainder of two numbers

def quotient_remainder(num1, num2):
    quotient = num1 // num2
    remainder = num1 % num2
    return quotient, remainder

print(quotient_remainder(17, 5))

Drill 6: Combining the concepts

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Implement a function that takes two linked lists representing numbers and returns a new linked list representing their sum.
# Assume the numbers are represented such that each of their digits is stored in reverse order.

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

def add_two_numbers(l1, l2):
    carry = 0
    root = n = ListNode(0)
    while l1 or l2 or carry:
        v1 = v2 = 0
        if l1:
            v1 = l1.val
            l1 = l1.next
        if l2:
            v2 = l2.val
            l2 = l2.next
        carry, val = divmod(v1 + v2 + carry, 10)
        n.next = ListNode(val)
        n = n.next
    return root.next

Thoroughly understand each drill before moving onto the next one. This step-by-step process will gradually build up your understanding of the final function.

Similar Problems

Remove Duplicates from Sorted List
Remove Duplicates from Sorted List II
Palindrome Linked List
Rotate List
Add Two Numbers
Reverse Linked List II
Linked List Cycle II
Copy List with Random Pointer
Reverse Nodes in k-Group

Remove Duplicates from Sorted List Given a sorted linked list, delete all duplicates such that each element appear only once.

For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3.

Solution We can just solve it like in an array using another index to collect the valid nodes.

Remove Duplicates from Sorted List II Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.

Solution Iterative

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
ListNode* deleteDuplicates(ListNode* head) {
	ListNode* dummy = new ListNode(0);
	dummy->next = head;
	ListNode* cur = dummy;
	int duplicate;
	while (cur->next && cur->next->next) {
		if (cur->next->val == cur->next->next->val) {
			duplicate = cur->next->val;
			while (cur->next && cur->next->val == duplicate) 
				cur->next = cur->next->next;
		}
		else cur = cur->next;
	}
	return dummy->next;
}

Recursive

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
ListNode* deleteDuplicates(ListNode* head) {
    if (!head) return 0;
    if (!head->next) return head;
    int val = head->val;
    ListNode* p = head->next;
    if (p->val != val) { head->next = deleteDuplicates(p); return head;} 
    else { 
        while (p && p->val == val) p = p->next; 
        return deleteDuplicates(p); 
    }
}

Palindrome Linked List Given a singly linked list, determine if it is a palindrome.

Follow up: Could you do it in O(n) time and O(1) space?

Solution Converting the linked list into an array to simplify the checking.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
bool isPalindrome(ListNode* head) {
    vector<int> v;
    while(head) {
        v.push_back(head->val);
        head = head->next;
    }
    for(int i = 0; i < v.size()/2; ++i) {
        if(v[i] != v[v.size()-i-1]) return false;
    }
    return true;
}

Do it using linked list:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool isPalindrome(ListNode* head) {
    if(!head || !head->next) return true;
    ListNode *slow = head, *fast = head->next;
    while(fast && fast->next) {//split into two halves while the first half can be one-node longer;
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;
    ListNode newHead(0); //reverse the second half;
    ListNode *next = NULL, *p = fast;
    while(p) {
        next = p->next;
        p->next = newHead.next;
        newHead.next = p;
        p = next;
    }
    fast = newHead.next; //compare the two lists;
    while(fast) {
        if(fast->val != head->val) return false;
        fast = fast->next;
        head = head->next;
    }
    return fast == NULL;
}

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
ListNode* rotateRight(ListNode* head, int k) {
    if(!head) return head;
    int len = 1;
    ListNode *p = head;
    while(p->next) { len++; p = p->next; }
    p->next = head;
    if(k %= len)
        for(int i = 0; i < len-k; ++i, p=p->next) ; 
    ListNode* newHead = p->next;
    p->next = NULL;
    return newHead;
}

Add Two Numbers You are given two linked lists representing two non-negative numbers. 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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

Solution Iterative

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    int c = 0;
    ListNode newHead(0);
    ListNode *t = &newHead;
    while(c || l1 || l2) {
        c += (l1? l1->val : 0) + (l2? l2->val : 0);
        t->next = new ListNode(c%10);
        t = t->next;
        c /= 10;
        if(l1) l1 = l1->next;
        if(l2) l2 = l2->next;
    }
    return newHead.next;
}

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    if(!l1 && !l2) return NULL;
    int c = (l1? l1->val:0) + (l2? l2->val:0);
    ListNode *newHead = new ListNode(c%10), *next = l1? l1->next:NULL;
    c /= 10;
    if(next) next->val += c;
    else if(c) next = new ListNode(c);
    newHead->next = addTwoNumbers(l2? l2->next:NULL, next);
    return newHead;
}

Reverse Linked List II Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.

Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
ListNode* reverseBetween(ListNode* head, int m, int n) {
    ListNode newHead(0);
    newHead.next = head;
    ListNode *pre = &newHead, *cur = head, *next = NULL;
    int i = 1;
    while(i < n) {
        if(i++ < m) { pre = cur; cur = cur->next; }
        else { 
            next = cur->next; 
            cur->next = cur->next->next; 
            next->next = pre->next; 
            pre->next = next; 
        }
    }
    return newHead.next;
}

Linked List Cycle II Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Note: Do not modify the linked list.

Follow up: Can you solve it without using extra space?

Solution Actually we can just use set.insert(key).second to check but it will take up O(n) space which is quite an awful waste, so here we just going to check the circle and then locate it.

If there is a circle then once the slow meets the fast the first time, there will be a formula as follows: a+b+kl = 2(a+b) -> kl-b = a (a is the length between the head and the start of the circle, b is the steps the slow pointer moves in the circle while l is the length of the circle). After that we can reset the fast and slow down the fast (same speed as the slow using kl-b = a) then once they meet again, the location will be the start of the circle. At last we take up constant space to solve this and traverse the linked list twice at most (as for the slow pointer).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
ListNode *detectCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;   
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast) break;
    }
    if(slow != fast) return NULL;
    fast = head;
    while(fast && fast->next) {
        if(slow == fast) return slow;
        slow = slow->next;
        fast = fast->next;
    }
    return NULL;
}

Copy List with Random Pointer linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list.

Recursive

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    unordered_map<RandomListNode*, RandomListNode*> cloneMap;
    RandomListNode *helper(RandomListNode* head){
        if(head == NULL) return NULL;
        if(cloneMap.count(head)) return cloneMap[head];
        RandomListNode *cloned = new RandomListNode(head->label);
        cloneMap[head] = cloned; //crucial;
        cloned->next = helper(head->next);
        cloned->random = helper(head->random);
        return cloned;
    }
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        return helper(head);
    } 
};

Iterative

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
RandomListNode *copyRandomList(RandomListNode *head) {
	RandomListNode newHead(0), *p = head, *t = NULL;
	while(p) {
		RandomListNode *cloned = new RandomListNode(p->label);
		cloned->next = p->next;
		p->next = cloned;
		p = cloned->next;
	}
	p = head;
	while(p && p->next) {
		if(p->random) p->next->random = p->random->next;
		p = p->next->next;
	}
	p = head;
	t = &newHead;
	while(p && p->next) {
		t->next = p->next;
		p->next = p->next->next;
		t = t->next;
		p = p->next;
	}
	t->next = NULL;
	return newHead.next;
}

Reverse Nodes in k-Group Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed. Only constant memory is allowed.

For example, Given this linked list: 1->2->3->4->5 For k = 2, you should return: 2->1->4->3->5 For k = 3, you should return: 3->2->1->4->5

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ListNode* reverseKGroup(ListNode* head, int k) {
	if(!head || !head->next) return head;
	ListNode newHead(0);
	ListNode *pre = &newHead, *cur = head, *next = NULL;
	newHead.next = head;
	int len = 0;
	for(ListNode *p = head; p; p = p->next) len++;
	int times = len/k;
	while(times) {
		for(int i = 1; i < k; ++i) {
			next = cur->next;
			cur->next = cur->next->next;
			next->next = pre->next;
			pre->next = next;
			if(i == k-1) {
				pre = cur;
				cur = cur->next;
			}
		}
		times--;
	}
	return newHead.next;
}