给定两个非空链表逆序存储的的非负整数,每个节点只存储一位数组。
请你把两个链表相加以下相同方法返回链表,保证两个数都不会以 0 开头。
数据范围: ,每个节点的值都满足
# -*- coding: utf-8 -*- class ListNode: def __init__(self, x): self.val = x self.next = None class LinkedList: def __init__(self): self.head = None def initLinkedList(self, nums): n = len(nums) if n > 0: self.head = ListNode(nums[0]) cur = self.head for i in range(1, n): cur.next = ListNode(nums[i]) cur = cur.next return self.head @staticmethod def printLinkedList(head): if not head: return [] cur, res = head, [] while cur: res.append(cur.val) cur = cur.next return res # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param l1 ListNode类 # @param l2 ListNode类 # @return ListNode类 # class Solution: """ 题目: https://www.nowcoder.com/practice/521d83306d964c1188639033eb59621d?tpId=196&tqId=40273&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D7%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title= 算法: 从前往后,遍历链表l1和l2,对于第i项相加和sum = h1.val + h2.val + carry,新建节点ListNode(sum % 10), 记录进位carry = sum / 10 复杂度: 时间复杂度:O(min(M, N) ~ max(M, N)) 空间复杂度:O(1) """ def ListAdd(self, l1, l2): # write code here if not l1: return l2 elif not l2: return l1 head1, head2, carry = l1, l2, 0 dummy = ListNode(-1) cur = dummy while head1 and head2: sum = head1.val + head2.val + carry cur.next = ListNode(sum % 10) carry = sum / 10 head1 = head1.next head2 = head2.next cur = cur.next while head1: if carry == 0: cur.next = head1 break sum = carry + head1.val cur.next = ListNode(sum % 10) carry = sum / 10 head1 = head1.next cur = cur.next while head2: if carry == 0: cur.next = head2 break sum = carry + head2.val cur.next = ListNode(sum % 10) carry = sum / 10 head2 = head2.next cur = cur.next if carry: # 链表遍历结束,仍有进位,如1 + 9 cur.next = ListNode(carry) return dummy.next if __name__ == "__main__": sol = Solution() # nums1, nums2 = [2, 5, 6], [5, 6, 1] # nums1, nums2 = [0], [1, 2, 3, 4, 5, 6] nums1, nums2 = [9, 9, 9], [9, 9, 0] # nums1, nums2 = [7, 5, 3, 5, 6, 2, 9, 1], [2, 7, 0, 9, 3, 6] # nums1, nums2 = [9, 9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9, 9, 9] l = LinkedList() l1, l2 = l.initLinkedList(nums1), l.initLinkedList(nums2) # print LinkedList.printLinkedList(l1), LinkedList.printLinkedList(l2) res = sol.ListAdd(l1, l2) print l.printLinkedList(res) # python2直接超时 无语的效率