Leetcode/prob2.cpp at main · CypherKingdom/Leetcode · GitHub

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
/*
	Medium - Add Two Numbers
	https://leetcode.com/problems/add-two-numbers/description
*/

/*
	Adding two non-negative integers represented as linked lists and
	returns their sum as a new linked list:
	Purpose:
	Each input linked list (l1 and l2) represents a number where digits are stored in reverse order (e.g., 123 is stored as 3 -> 2 -> 1).
	The task is to calculate the sum of these numbers digit by digit, accounting for any carry, and return the result as a linked list.
	Key Steps:
	Initialization: A carry variable is introduced to handle cases where the sum of digits exceeds 9.
	For example, summing 7 and 8 results in carry = 1 for the next step.
	The loop processes corresponding digits of l1 and l2 by adding them along with the current carry.
	A new node is created for each digit of the resulting sum (modulo 10), and the carry is updated as sum / 10.
	Edge Cases:
	If one list becomes nullptr before the other, the remaining digits of the other list are processed.
	If there's a leftover carry after processing both lists, it is added as a new node at the end.
	Efficiency:
	The function processes each node in both linked lists exactly once, resulting in a time complexity of O(max(n, m)),
	where n and m are the lengths of l1 and l2, respectively.
	Result:
	The function constructs a new linked list where each node represents a digit of the sum, stored in reverse order
	(consistent with the input format).
*/

using namespace std;

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

class Solution
{
public:
	ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
	{
		ListNode *l1_head = l1;
		ListNode *l2_head = l2;
		int carry = 0, x, y;
		if (l1 == nullptr)
			x = l2->val + carry;
		else if (l2 == nullptr)
			x = l1->val + carry;
		else
			x = l1->val + l2->val + carry;
		carry = 0;
		y = x % 10;
		carry = x / 10;
		ListNode *l3 = new ListNode(y);
		ListNode *l3_head = l3;
		l3_head->next = l3->next;
		if (l1 != nullptr)
			l1 = l1->next;
		if (l2 != nullptr)
			l2 = l2->next;
		while (l1 != nullptr || l2 != nullptr)
		{
			if (l1 == nullptr)
				x = l2->val + carry;
			else if (l2 == nullptr)
				x = l1->val + carry;
			else
				x = l1->val + l2->val + carry;
			carry = 0;
			y = x % 10;
			carry = x / 10;
			l3->next = new ListNode(y);
			l3 = l3->next;
			if (l1 != nullptr)
				l1 = l1->next;
			if (l2 != nullptr)
				l2 = l2->next;
		}
		if (carry != 0)
			l3->next = new ListNode(carry);
		return l3_head;
	}
};