Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

2. Add two numbers

2. Add two numbers, medium

I. Title Description:

And when you look at them, it gives you the impression that you’re adding these two numbers, right? What? Isn’t that just adding two numbers? It’s not that hard. It’s not that hard

However, after carefully reviewing the specific topic content and specific examples, I feel quite simple, but I do not know how to write, if the C language foundation is poor brothers (do not know how to play the kind of linked list), this question may not be very easy to write

However, this problem is also relatively simple, there is a certain basis of C language brothers, brush up soSO, no pressure, but we still to analyze and deduce, not the brothers, can also be

Ii. Analysis of Ideas:

1. What ideas does this question examine? What’s your thinking?

Let’s take a look at what the question reveals:

• Both lists are non-empty and represent integers, not negative numbers
• Each node of the list will hold only one integer, the number is 1 digit, and the entire list will not start with a 0, unless there is only one node in the list, which can be a 0
• The order of the linked list is reversed from the order of the numbers normally given, with the highest digit at the end of the list and the lowest digit at the head

With this information in mind, we can use normal integers to simulate and deduce:

Take example 3 as an example:

Input: l1 =,9,9,9,9,9,9 [9], l2 =,9,9,9 [9] output:,9,9,9,0,0,0,1 [8]Copy the code

As can be seen from the figure, it is actually a variation of the basic addition problem learned in primary school. We just flipped the numbers this time, changing the high level to the right and the low level to the left

So when we carry, we used to carry 1 to the left, and now we have to carry 1 to the right

Then evolved to the linked list, the logic is complete, the rest is really just the implementation of the coding problem, the poor foundation of the brothers may not be very good to write, but nothing, more practice, more practice, more thinking, you get used to it

2. Try coding

According to the above logic and deduction, in fact, the idea is very simple, is 2 numbers corresponding to each bit, pay attention to the carry problem, pay attention to the high right problem can be

// The list returned first specifies a header pointer
func addTwoNumbers(l1, l2 *ListNode) (head *ListNode) {
    // Define a tail pointer
    var tail *ListNode
    // Carry, default is 0
    carry := 0
    // Check two lists. If one of the lists is empty, exit the loop
    forl1 ! =nil|| l2 ! =nil {
        n1, n2 := 0.0
        ifl1 ! =nil {
            n1 = l1.Val
            l1 = l1.Next
        }
        ifl2 ! =nil {
            n2 = l2.Val
            l2 = l2.Next
        }
        sum := n1 + n2 + carry
        sum, carry = sum%10, sum/10
        if head == nil {
            head = &ListNode{Val: sum}
            tail = head
        } else {
            tail.Next = &ListNode{Val: sum}
            tail = tail.Next
        }
    }
    // The basic list has been formed, and the last bit is checked to see if there is a carry bit. If there is a carry bit, the last bit is put at the end of the list
    if carry > 0 {
        tail.Next = &ListNode{Val: carry}
    }
    return
}
Copy the code

In this case, the corresponding comment has been written in the code, but let me briefly say:

• So to start, I’m going to create a head pointer, head, and a tail pointer
• After verifying that the linked list meets the conditions, the header pointer data of the two linked lists are taken out respectively and added. If there is carry, the carry will be copied to carry
• If head is empty, the result is given to head, and tail also points to head (because there is only one node in the list).
• If head is not empty, pass the result to the next node on tail, and then point tail to the current tail node

Iv. Summary:

Although this question is a medium type of question, but the idea is relatively simple and clear, compared with other medium questions is not so complex, just need to consider the details and carry problem

In this case, the time complexity is O(Max (m,n)), where m and n represent the length of the two lists. The complexity of the two lists depends on which one is longer

The space complexity is O(Max (m,n)). If the resulting list is longer than the length given in the two lists, then it is only a round. The longest space complexity is O(Max (m,n) + 1).

2. Add two numbers

Today is here, learning, if there is a deviation, please correct

Welcome to like, follow and favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~