This is the 17th day of my participation in the Gwen Challenge.More article challenges

For a better tomorrow, keep brushing LeetCode!

The 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, 3], l2 =,6,4 [5] output:,0,8 [7] : 342 + 465 = 807.Copy the code

Example 2:

Input: L1 = [0], L2 = [0] Output: [0]Copy the code

Example 3:

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

Solution number one – cycle of violence

Their thinking

First, it is clear that the two numbers are stored in reverse order, so that the head node points to the last digit of each number (i.e., the units digit). Then we can add the Val of the two linked head nodes and point the two linked head nodes to their child nodes Next respectively.

And of course, when we add, we also have the carry problem, which is equal to n1 plus n2 plus carry over 10.

code

We use head to denote the head node of the output list, and tail always points to the last node of the output list:

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
func addTwoNumbers(l1, l2 *ListNode) (head *ListNode) {
    var tail *ListNode
    carry := 0
    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
        }
    }
    if carry > 0 {
        tail.Next = &ListNode{Val: carry}
    }
    return
}
Copy the code

The execution result

Execution time: 24 ms, beat 10.96% of users in all Go commits memory consumption: 4.7 MB, beat 22.11% of users in all Go commitsCopy the code

Complexity analysis

  • Time complexity: O(Max (m,n)), wherem 和 nAre the lengths of two linked lists. We’re going through all the positions on both lists, and it only takes O(1) time to process each position.
  • Space complexity: O(1). Note that the returned value does not count space complexity.

Solution two – recursion

Their thinking

From solution 1, we can find that each loop adds two numbers in the same place and calculates the carry value. Then we can write a recursive function and pass each carry as an argument:

  • A recursive function returns the sum of two numbers in the same bit
  • The recursive function is incarryIs zero, and terminates when one or both lists are empty

code

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
func addTwoNumbers(l1, l2 *ListNode) (head *ListNode) {
    return add(l1, l2, 0)}func add(l1, l2 *ListNode, carry int) *ListNode {
    if l1 == nil && l2 == nil && carry == 0 {
        return nil
    }
    ifl1 ! =nil && l2 == nil && carry == 0 {
        return l1
    }
    ifl2 ! =nil && l1 == nil && carry == 0 {
        return l2
    }

    sum := carry
    ifl1 ! =nil {
        sum += l1.Val
        l1 = l1.Next
    }
    ifl2 ! =nil {
        sum += l2.Val
        l2 = l2.Next
    }
    sum, carry = sum%10, sum/10
    node := &ListNode{Val: sum}
    node.Next = add(l1, l2, carry)
    return node
}
Copy the code

The execution result

Execution time: 16 ms, beat 38.47% of users memory consumption: 4.7 MB, beat 12.74% of users in all Go commitsCopy the code

Complexity analysis

  • Time complexity: O(min(m,n)), wherem 和 nAre the lengths of two linked lists. The recursion terminates when one or both lists are empty.
  • Space complexity: O(min(m,n)).

Topic link

2. Add two numbers