Hello, I’m Liang Tang.

Today I’m going to give you LeetCode number two, adding two numbers, which is a Medium difficulty problem. Github, explaining videos

The question

The problem is very simple, given two non-empty linked lists. Representing an integer in reverse order requires us to add the two numbers and return a linked list of the same form.

Neither of these numbers will start with a 0, with no leading 0, except for the number 0.

The so-called reverse linked list, as shown in the problem, is in the following form:

Let’s say 2 -> 4 -> 3, we’re storing 342, not 243, so we have to pay attention here.

Data range

  • The number of nodes in each linked list is in the range[1, 100] 内
  • 0 <= Node.val <= 9
  • The question data ensures that the numbers represented in the list do not contain leading zeros

solution

The problem itself is very simple, the difficulty is the use of linked lists.

As we know, in C++ we have the concept of Pointers, which can point to the memory address of a variable. By using Pointers, we can design a special data structure that stores a pointer to a structure of the same type. In this way, we can connect several instances of a structure, like a chain, through Pointers in the structure. This data structure is called a linked list.

We can look at the definition of the linked list given in the problem:

Some students asked me before, where did you get the structure you used, and I didn’t see your definition. In fact, this is a lot of OJ characteristics, we need to implement the core logic, sometimes write a function, sometimes write a class. In addition to the code we write, the referee runs a lot of other logic. It’s just that the logic has nothing to do with our problem, so it’s all hidden.

For example, the list definition here, LeetCode has already defined it for us. We just need to use it, and we don’t really care where it’s defined.

Let’s take a look at this structure. It’s called a ListNode, and as the name implies, it represents the nodes of a linked list. It has two member variables, val of type int and a pointer to ListNode. Val stores an integer between 0 and 9, representing one of the digits of an integer. The pointer is used to point to the next node.

Let’s look at the function we want to implement:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
Copy the code

Two arguments are passed in, the first Pointers to two lists, and the result to be returned is also a pointer. Is the header pointer to our new linked list.

So we need to do two things, one is to iterate through the two lists L1 and L2, and the second is to add the numbers to generate a new list and return a new list header pointer.

Unlike arrays, there is no way to know the exact length of a linked list. We can only iterate through it using a while loop, moving the start nodes one by one and stopping when we reach a null pointer. In this case we need to iterate over two linked lists, so the loop condition should look like this:

while(l1 ! =nullptr|| l2 ! =nullptr) {
    // todo
}
Copy the code

After walking through the list, all that’s left is an easy addition. At this point, we will find that reverse storage of the linked list is very beneficial. Because every element that we take it has a certain position, the first one has to be the place, and the second one has to be the tens place. If our list is stored in positive order, we don’t know which digit is the first digit until we know the length of the list.

So on the surface, it might seem like a hassle to store a linked list in reverse order, but it actually simplifies things for us.

Finally, we just need to pay attention to the addition of the carry, it is easy to write code:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* ret = new ListNode(a); ListNode* pnt = ret;bool carry = false;
        while(l1 ! =nullptr|| l2 ! =nullptr || carry) {
            int cur = 0;
            if(l1 ! =nullptr) {
                cur += l1->val;
                l1 = l1->next;
            }
            if(l2 ! =nullptr) {
                cur += l2->val;
                l2 = l2->next;
            }
            if (carry) {
                cur ++;
            }
            if (cur >= 10) {
                cur -= 10;
                carry = true;
            }else {
                carry = false;
            }
            pnt->next = new ListNode(cur);
            pnt = pnt->next;
        }
        returnret->next; }};Copy the code

There’s nothing to say about the carry, the only thing to notice is that the condition in the while loop has a judgment about whether or not to carry. This is what happens when the carry of the highest bit occurs, otherwise the carry of the highest bit is lost.

As long as you pay attention to this trick, and understand the basic use of linked lists, this problem will be solved, is not very simple?

All right, that’s it. Thank you for reading.