[Swift]LeetCode445.两数相加II|AddTwoNumbersII

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10339558.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶:

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例:

输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

64ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
14         var n1:Int = getLength(l1)
15         var n2:Int = getLength(l2)
16         var head:ListNode? = ListNode(1)
17         head!.next = (n1 > n2) ? helper(l1, l2, n1 - n2) : helper(l2, l1, n2 - n1)
18         if head!.next!.val > 9
19         {
20             head!.next!.val %= 10
21             return head
22         }
23         return head!.next
24     }
25     
26     func getLength(_ head: ListNode?) -> Int
27     {
28         var head = head
29         var cnt:Int = 0
30         while(head != nil)
31         {
32             cnt += 1
33             head = head!.next
34         }
35         return cnt
36     }
37     
38     func helper(_ l1: ListNode?, _ l2: ListNode?,_ diff:Int) -> ListNode?
39     {
40         if l1 == nil {return nil}
41         var res:ListNode? = (diff == 0) ? ListNode(l1!.val + l2!.val) : ListNode(l1!.val)
42         var post:ListNode? = (diff == 0) ? helper(l1!.next, l2!.next, 0) : helper(l1!.next, l2, diff - 1)
43         if post != nil && post!.val > 9
44         {
45             post!.val %= 10
46             res!.val += 1
47         }
48         res!.next = post
49         return res
50     }
51 }

92ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {    
13 func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode?       {
14     var array1: [Int] = []
15     var array2: [Int] = []
16     var array3: [Int] = []
17     var list1 = l1, list2 = l2
18     
19     while list1 != nil {
20         array1.append(list1!.val)
21         list1 = list1?.next
22     }
23     
24     while list2 != nil{
25         array2.append(list2!.val)
26         list2 = list2?.next
27     }
28     
29     var flag = 0
30     while array1.last != nil || array2.last != nil {
31         var sum = (array1.popLast() ?? 0) + (array2.popLast() ?? 0) + flag
32         if sum >= 10{
33             flag = 1
34             sum = sum - 10
35         }else{
36             flag = 0
37         }
38         array3.append(sum)
39     }
40     if flag == 1{
41         array3.append(1)
42     }
43     let list3: ListNode? = ListNode(-1)
44     var list4 = list3
45 
46     while array3.last != nil{
47         list4?.next = ListNode(array3.popLast()!)
48         list4 = list4?.next
49     }
50     return list3?.next
51  }
52 }

100ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
14         guard let l1 = l1, l1.val != 0 else {
15             return l2
16         }
17 
18         guard let l2 = l2, l2.val != 0 else {
19             return l1
20         }
21 
22         var next: ListNode? = l1
23         var nums1: [Int] = []
24         while next != nil {
25             nums1.append(next!.val)
26             next = next?.next
27         }
28 
29         var next2: ListNode? = l2
30         var nums2: [Int] = []
31         while next2 != nil {
32             nums2.append(next2!.val)
33             next2 = next2?.next
34         }
35 
36         let loopCount = max(nums1.count, nums2.count)
37         next = l1
38         if nums1.count < nums2.count {
39             let temp = nums2
40             nums2 = nums1
41             nums1 = temp
42             next = l2
43         }
44 
45         let count = nums1.count
46 
47         for index in 0..<loopCount {
48             var num2 = 0
49             let index2 = nums2.count - 1 - index
50             if index2 >= 0 {
51                 num2 = nums2[index2]
52             }
53 
54             let sum = nums1[nums1.count - 1 - index] + num2
55             if sum >= 10 {
56                 nums1[nums1.count - 1 - index] = sum % 10
57                 if nums1.count - 2 - index < 0 {
58                     nums1.insert(1, at: 0)
59                 } else {
60                     nums1[nums1.count - 2 - index] += 1
61                 }
62             } else {
63                 if index2 < 0 {
64                     break
65                 }
66                 
67                 nums1[nums1.count - 1 - index] = sum
68             }
69         }
70 
71         var root: ListNode!
72         var index = 0
73         if count < nums1.count {
74             root = ListNode(nums1[0])
75             root.next = next
76             index = 1
77         } else {
78             root = next
79         }
80 
81         while index < nums1.count {
82             next?.val = nums1[index]
83             next = next?.next
84             index += 1
85         }
86 
87         return root
88     }
89 }

124ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     func reverse(_ list: ListNode?) -> ListNode?{
14     var l1 = list
15     var pre: ListNode? = nil
16     while l1 != nil {
17         let temp = l1?.next
18         l1?.next = pre
19         pre = l1
20         l1 = temp
21     }
22     return pre
23 }
24     
25 func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode?       {
26     let list1 = self.reverse(l1)
27     let list2 = self.reverse(l2)
28     let list3: ListNode? = ListNode(-1)
29     
30     var ll1 = list1, ll2 = list2, ll3 = list3
31     var flag = 0
32     while ll1 != nil || ll2 != nil{
33         let ll1value = ll1?.val ?? 0
34         let ll2value = ll2?.val ?? 0
35         var sum = ll1value + ll2value + flag
36         if sum >= 10{
37             flag = 1
38             sum = sum - 10
39         }else{
40             flag = 0
41         }
42         ll3?.next = ListNode(sum)
43         ll3 = ll3?.next
44         ll2 = ll2?.next
45         ll1 = ll1?.next
46     }
47     if flag == 1{
48         ll3?.next = ListNode(1)
49     }
50     return self.reverse(list3?.next)
51   }
52 }

156ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
14         var rl1 = reverseList(l1)
15         var rl2 = reverseList(l2)
16         
17         var rres = addTwoNumbers1(rl1, rl2)
18         
19         return reverseList(rres)
20     }
21     
22     func reverseList(_ head: ListNode?) -> ListNode? {
23         var cur = head
24         var pre: ListNode? = nil
25         
26         while cur != nil {
27             var next = cur!.next
28             cur!.next = pre
29             pre = cur
30             cur = next
31         }
32         
33         return pre
34     }
35     
36     func addTwoNumbers1(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
37         var cur1 = l1
38         var cur2 = l2
39         var head: ListNode? = nil
40         var pre: ListNode? = nil
41         
42         var carryBit = 0
43         
44         while cur1 != nil || cur2 != nil {
45             var sum: Int;
46             if cur1 != nil && cur2 != nil {
47                 sum = cur1!.val + cur2!.val + carryBit
48                 cur1 = cur1!.next
49                 cur2 = cur2!.next
50             } else if cur1 != nil && cur2 == nil {
51                 sum = cur1!.val + carryBit
52                 cur1 = cur1!.next
53             } else {
54                 sum = cur2!.val + carryBit
55                 cur2 = cur2!.next
56             }
57             
58             carryBit = sum / 10
59             let reminder = sum % 10
60             
61             let newNode = ListNode(reminder)
62             
63             if pre == nil {
64                 head = newNode
65             } else {
66                 pre?.next = newNode
67             }
68             
69             pre = newNode
70         }
71         
72         if carryBit > 0 {
73             let newNode = ListNode(carryBit)
74             pre?.next = newNode
75         }
76         
77         return head
78     }
79 }

224ms

  1 /**
  2  * Definition for singly-linked list.
  3  * public class ListNode {
  4  *     public var val: Int
  5  *     public var next: ListNode?
  6  *     public init(_ val: Int) {
  7  *         self.val = val
  8  *         self.next = nil
  9  *     }
 10  * }
 11  */
 12 class Solution {
 13     func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
 14        
 15         var ls1Count = self.getListNodeArray(l1);
 16         var ls2Count = self.getListNodeArray(l2);
 17         var maxCount = max(ls1Count.count, ls2Count.count)
 18         var carry = 0
 19         var startNode : ListNode?
 20         var nextNode : ListNode?
 21         for i in 0..<maxCount{
 22             
 23             if(i >= ls1Count.count || i >= ls2Count.count)
 24             {
 25                 var val : Int = carry
 26                 if(i >= ls1Count.count)
 27                 {
 28                     val  += ls2Count[i]
 29                 }
 30                 else
 31                 {
 32                     val  += ls1Count[i]
 33                 }
 34                 if(val >= 10 )
 35                 {
 36                     val = val % 10
 37                     carry = 1
 38                 }
 39                 else {
 40                     carry = 0
 41                 }
 42                 let node = ListNode.init(val)
 43                 nextNode?.next = node
 44                 nextNode = node;
 45                 print(val);
 46             }
 47             else
 48             {
 49                 var val = ls2Count[i] + ls1Count[i] + carry
 50                 if(val >= 10 )
 51                 {
 52                     val = val % 10
 53                     carry = 1
 54                 }
 55                 else {
 56                     carry = 0
 57                 }
 58                 print(val);
 59                 let node = ListNode.init(val);
 60                 if(startNode  == nil)
 61                 {
 62                     startNode = node;
 63                 }
 64                 else
 65                 {
 66                     nextNode!.next = node;
 67                 }
 68                 nextNode = node;
 69                 
 70             }
 71         }
 72         if(carry == 1)
 73         {
 74             let node = ListNode.init(1);
 75             nextNode?.next = node;
 76         }
 77         let des  = self.getListNodeArray(startNode);
 78         var next2Node : ListNode?
 79         var start2Node : ListNode?
 80         for val in des{
 81                 
 82             let node = ListNode.init(val);
 83             if(start2Node  == nil)
 84             {
 85                 start2Node = node;
 86             }
 87             else
 88             {
 89                 next2Node!.next = node;
 90             }
 91             next2Node = node;
 92             
 93         }
 94         
 95         return start2Node;
 96         
 97     }
 98     
 99     
100     func getListNodeArray(_ ls : ListNode?) -> [Int] {
101         var lsCount :[Int] = []
102         var nls = ls;
103         while( nls != nil  )
104         {
105             lsCount.append(nls?.val as! Int)
106             nls = nls?.next
107         }
108         
109         var desCount : [Int] = []
110         for (index,value) in lsCount.enumerated().reversed() {
111             
112             desCount.append(value)
113          
114         }
115         
116         return desCount
117     }
118 }