“This is the second day of my participation in the November Gwen Challenge. See details of the event: The last Gwen Challenge 2021”.

preface

I have been planning to learn data structures and basic algorithms, but I have seen them in fits and starts. Now I’m determined to stick to it. I’m going to start with LeetCode’s HOT100 and finish 1~2 exercises every day, hoping to develop the habit of continuous learning in this way. Because I am doing iOS development, mainly using Objective-C language, and I am also learning Swift recently, all the questions in this series will be solved using Swift language. What is updated in this paper is the addition of two numbers in the second question 002 of HOT100 in 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,4,3], l2 = [5,6,4] output: [7,0,8] explanation: 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

Analysis of the

In this case, the sum of the numbers in the same position in the two lists can be added directly because the input lists store the digits in reverse order. We iterate over both lists at the same time, calculating their sum bit by bit and adding it to the carry value of the current position. Specifically, if the numbers at the corresponding positions of the current two linked lists are N1 and n2, and the carry value is CARRY, their sum is N1 +n2+ CARRY; Where, the corresponding number in the answer list is (N1 +n2+carry)mod10 (where mod means remainder), and the new carry value is (n1+n2+carry)/10 (where division/means full division). If two lists are of different lengths, the short list can be considered to be followed by several zeros. In addition, if the list has carry>0 after traversal, you also need to append a node to the answer list with a value of CARRY.

Answer key

/** * Definition for singly-linked list. * public class ListNode { * public var val: Int * public var next: ListNode? * public init() { self.val = 0; self.next = nil; } * public init(_ val: Int) { self.val = val; self.next = nil; } * public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }} * * / 
class Solution {
     func addTwoNumbers(_ l1: ListNode? ._ l2: ListNode?). -> ListNode? {
         // If one of the linked lists is empty, the other list can be returned without calculation
         if l1 = = nil { return l2 } 
         if l2 = = nil { return l1 } 
         var addVal = 0  // Carry the value carry
         var curl1 = l1  // The current value of list 1 is n1
         var curl2 = l2  // List 2 has the current value n2
         var curResNode:ListNode? = nil // Results the current node of the linked list
         var ansNode :ListNode? = nil  // The header of the result list
         while curl1 ! = nil || curl2 ! = nil || addVal ! = 0 {
             let tempAns = (curl1?.val ?? 0) + (curl2?.val ?? 0) + addVal 
             addVal = tempAns / 10  // Computes the values in the carry
             let node = ListNode(tempAns%10)  // Create the current result node
             if curResNode = = nil { 
                 ansNode = node 
                 curResNode = node 
             } else { 
                 curResNode?.next = node 
                 curResNode = node 
             } 
             // Continue next
             curl1 = curl1?.next 
             curl2 = curl2?.next 
         } 
         curResNode?.next = nil 
         return ansNode 
     } 
}
Copy the code