Classic 150 Interview Questions P2 Add Two Numbers

---

Timeline

Timeline

2025-11-19

init

linked list

---

Problem:

P2 Add Two Numbers

https://leetcode.cn/problems/add-two-numbers/description/?envType=study-plan-v2&envId=top-interview-150

Note the carry on the last digit

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)
	{
	}
};
class Solution {
    public:
	ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
	{
		ListNode *p1 = l1, *p2 = l2;
		ListNode *l3 = new ListNode;
		ListNode *p3 = l3;
		int carry = 0, total, val1, val2;

		while (p1 != nullptr || p2 != nullptr) {
			if (p1 == nullptr) {
				val1 = 0;
			} else {
				val1 = p1->val;
				p1 = p1->next;
			}

			if (p2 == nullptr) {
				val2 = 0;
			} else {
				val2 = p2->val;
				p2 = p2->next;
			}

			total = val1 + val2 + carry;
			p3->val = total % 10;

			if (!(p1 == nullptr && p2 == nullptr)) { //The last one has no Next
				p3->next = new ListNode;
				p3 = p3->next;
			}
			carry = total / 10;
		}
		if (carry != 0) {
			p3->next = new ListNode;
			p3 = p3->next;
			p3->val = carry;
		}

		return l3;
	}
};

leetcode hot100 rewrite:

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */

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)
        {
        }
};

class Solution {
    public:
        ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
        {
                ListNode *virtual_head = new ListNode;
                ListNode *tail = virtual_head;

                int offset = 0, value;
                while (l1 || l2) {
                        if (l1 && l2) {
                                value = l1->val + l2->val + offset;
                                l1 = l1->next;
                                l2 = l2->next;
                        } else if (l1 && !l2) {
                                value = l1->val + offset;
                                l1 = l1->next;
                        } else if (!l1 && l2) {
                                value = l2->val + offset;
                                l2 = l2->next;
                        }

                        tail->next = new ListNode(value % 10, nullptr);
                        tail = tail->next;

                        offset = value / 10;
                }
                if (offset != 0)
                        tail->next = new ListNode(offset, nullptr);

                tail = virtual_head->next;
                delete virtual_head;

                return tail;
        }
};

#include <vector>
using std::vector;

ListNode *build_list(vector<int> vec)
{
        ListNode *vitual_head = new ListNode;
        ListNode *tail = vitual_head;

        for (int val : vec) {
                tail->next = new ListNode(val, nullptr);
                tail = tail->next;
        }

        tail = vitual_head->next;
        delete vitual_head;
        return tail;
}

int main()
{
        vector<int> vec1 = { 2, 4, 9 };
        vector<int> vec2 = { 5, 6, 4, 9 };
        ListNode *list1 = build_list(vec1), *list2 = build_list(vec2);

        Solution S;
        S.addTwoNumbers(list1, list2);
}