Leetcode 2. Add two numbers in a linked list

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

1. Title 📑

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.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]

Output:,0,8 [7]

Explanation: 342 + 465 = 807.

Example 2:

Input: L1 = [0], L2 = [0]

Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9], l2 = [9,9,9,9]

Output:,9,9,9,0,0,0,1 [8]

Limitations:

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

2. Ideas 🧠

Method 1: carry problem of mathematical solution

  1. Sentence:
    • ifl1 == null && l2 == nullIt returns null
    • ifl1 == nullReturns linked list 2
    • ifl2 == nullReturns linked list 1
  2. Initialization: definitionListNode result The head of the linked listA header with a value of 0; defineListNode resultCur Point to the listresultThe head of thehead
  3. Circular judgment:l1 ! = null || l2 ! = null || carry ! = 0If all conditions are not met, the loop exits.
    • l1Val l2ValIf the list is empty, the value of that bit is replaced by 0
    • sumFind the sum of the current two lists. Note that there will be a round operation, and you need to add the result of the round
    • carry = sum / 10Find the next carry digit and save it to the next digit for the sum
    • ListNode t = new ListNode(sum % 10)Change the number of the current position toStore one digit
    • resultCur.next = t resultCur = resultCur.nextAdd the number of the current position to the new linked list defined previously, and continue moving backwards
    • At the same time, the linked list nodes that are not empty are also moved back
  4. returnresultThe next node of the.

Method two: use the stack to solve the summation

And you see that from left to right it’s -ten-hundred-thousand, starting in the ones place, just like method one

Method three: recursive summation

When you see that you’re adding the values of the two nodes at a time, and you’re adding the values of the carry, you can define a function that adds them up in pairs.

  1. Sentence:
    • ifl1 == null && l2 == null && carryNumReturns null, recursive end condition
  2. Case by case
    • If list 2 is empty, the value of list 1 is the value of the list node when it is mod, and the list moves later
    • If list 1 is empty, the value of list 2 is the value of the list node when it is mod, and the list moves later
  3. Start recursion, put the next two linked list nodes to be calculated and carry into the method, recursive operation.
  4. The sum is completed by returning the head node.

Less nonsense ~~~~~ on the code!

3. Code: 👨💻

Commit AC for the first time

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; }} * * /
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null && l2 == null) return null;
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode result = new ListNode(0);
        ListNode resultCur = result;
        int carry = 0; // Whether to carry
        while(l1 ! =null|| l2 ! =null|| carry ! =0) {
            int l1Val = l1 == null ? 0 : l1.val;
            int l2Val = l2 == null ? 0 : l2.val;
            int sum = l1Val + l2Val + carry;
            carry = sum / 10;/ / carry

            ListNode t = new ListNode(sum % 10);
            
            resultCur.next = t;
            resultCur = resultCur.next;

            if(l1 ! =null) l1 = l1.next;
            if(l2 ! =null) l2 = l2.next;
        }
        returnresult.next; }}/ / 9999999
/ / 0009999
/ / 10009998
Copy the code

Time complexity: O(Max (M, N)) where M and N are the lengths of two linked lists respectively.

Space complexity: O(Max (M, N))

Commit the SECOND TIME

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; }} * * /
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null && l2 == null) return null;
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode result = new ListNode(0);
        ListNode resultCur = result;
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        int carry = 0; // Whether to carry
        while(l1 ! =null|| l2 ! =null|| carry ! =0) {
            s1.push(l1 == null ? 0 : l1.val);
            s2.push(l2 == null ? 0 : l2.val);
            int sum = s1.pop() + s2.pop() + carry;
            carry = sum / 10;/ / carry

            ListNode t = new ListNode(sum % 10);
            resultCur.next = t;

            resultCur = resultCur.next;

            if(l1 ! =null) l1 = l1.next;
            if(l2 ! =null) l2 = l2.next;
        }
        returnresult.next; }}/ / 9999999
/ / 0009999
/ / 10009998
Copy the code

Time complexity: O(Max (M, N)) where M and N are the lengths of two linked lists respectively.

Space complexity: O(Max (M, N))

Commit AC for the third time

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; }} * * /
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return add(l1, l2, 0);
    }

    public ListNode add(ListNode l1, ListNode l2,int carryNum) {
        if(l1 == null && l2 == null && carryNum == 0) return null;
        
        int carry = carryNum;
        if(l1 ! =null) {
            carry += l1.val;
            l1 = l1.next;
        }

        if(l2 ! =null) {
            carry += l2.val;
            l2 = l2.next;
        }

        ListNode node = new ListNode(carry % 10);
        node.next = add(l1, l2, carry / 10);
        returnnode; }}Copy the code

Time complexity: O(Max (M, N)) where M and N are the lengths of two linked lists respectively.

Space complexity: O(Max (M, N))

4, summarize

This topic examines the concepts of recursion and mathematics in many knowledge points. The biggest difficulty lies in whether to understand the structure of the linked list. There is a carry problem in the addition of a number, which is particularly easy to ignore when carrying, resulting in the failure of the calculation results.

5. Related operations of linked lists

Link to 🔗

18. Remove list nodes – nuggets

Leetcode 21. Merge two ordered lists – nuggets

22. The k node from the bottom of the list – nuggets

Sword finger Offer 24. Reverse the list – nuggets

❤️ from the LeetCode Basic Algorithms column subscribe to ❤️

The original intention of the director to write blog is very simple, I hope everyone in the process of learning less detours, learn more things, to their own help to leave your praise 👍 or pay attention to ➕ are the biggest support for me, your attention and praise to the director every day more power.

If you don’t understand one part of the article, you can reply to me in the comment section. Let’s discuss, learn and progress together!

2. Add two numbers – LeetCode (leetcode-cn.com)