时间轴

2025-11-19

init

题目：

P2 两数相加

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

注意最后一位的进位

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

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)) { //最后一个没有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;
	}
};

hot100 rewrite

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/**
 * 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);
}