2. Add two numbers

Hello everyone, I’m Programming bear. Today is the second day of LeetCode’s daily problem. Together we will learn LeetCode’s second problem “Add Two numbers”.

The question

You are given two non-empty linked lists representing two non-negative integers. Each digit is stored in reverse order, and only one digit can be stored per node.

You add the two numbers and return a linked list representing the sum in the same form.

You can assume that neither of these numbers will start with 0, except for the number 0.

The sample

Input: l1 = [2, 3], l2 =,6,4 [5] output:,0,8 [7] : 342 + 465 = 807.Copy the code

Answer key

Since lists are in reverse order, the two lists can be added bit by bit from the beginning, but the two lists may not be the same length. For short lists, zeros can be added in high order. Note that after traversing both lists, the highest bit is carried and an extra bit is added.

Time complexity: O(n)O(n)O(n), where n is the longer length of the two lists.

Space complexity: O(1)O(1)O(1)

Summary of knowledge points: linked list

C + + code

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode* head = new ListNode(a); ListNode* currentPos = head;int v = 0;
        while(l1 || l2 || v) {
            int v1 = l1 ? l1->val : 0, v2 = l2 ? l2->val : 0;
            int res = (v + v1 + v2) / 10;
            v = (v1 + v2 + v) % 10;
            currentPos->val = v;
            v = res;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
            if (l1 || l2 || v) {
                currentPos->next = new ListNode();
                currentPos = currentPos->next;
            }
        }
        returnhead; }};Copy the code

Java code

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode currentPos = head;
        int v = 0;
        while(l1 ! =null|| l2 ! =null|| v ! =0) {
            intv1 = l1 ! =null ? l1.val : 0;
            intv2 = l2 ! =null ? l2.val : 0;
            int res = (v + v1 + v2) / 10;
            v = (v + v1 + v2) % 10;
            currentPos.val = v;
            v = res;
            if(l1 ! =null) l1 = l1.next;
            if(l2 ! =null) l2 = l2.next;
            if(l1 ! =null|| l2 ! =null|| v ! =0) {
                currentPos.next = newListNode(); currentPos = currentPos.next; }}returnhead; }}Copy the code

Title link: https://leetcode-cn.com/problems/add-two-numbers/

I am a programming bear, committed to making everyone a better person, welcome to “follow”, “like”, “forward” support ~