002——两数相加

1.题目

2.我的解决方案

2.1第一次解决方案

• 思路：
  • 从长度入手，计算链表长度，通过指针交换，固定l2为较长的那一个
  • 链表长度相等时，为了防止遍历到最后一个节点l2=l2.next=None，但是此时最高位向下一位产生进位，无法再添加结点情况，while循环到次高位节点，最高位的加法单独处理
  • l2链表长时，先计算公共部分的加法，结束之后，为了防止出现1+999这样的连续进位，循环验证l2,同上，为了防止最高位向下一位进位而指针l2=l2.next=None而无法添加结点的情况，将l2的最高位做单独的处理

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def getLength(l):   # 计算单链表长度
    length = 0
    if not l:
        return 0
    else:
        while l:
            length += 1
            l = l.next
        return length
        
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        length1 = getLength(l1)
        length2 = getLength(l2)
        flag = False
        if length1 > length2:   # 保持l2为长链表
            l3 = l1
            l1 = l2
            l2 = l3

        l3 = l2     # 直接在l2上相加，l3指向l2
        if length1 == length2:  # 当长度相同时
            while l1.next:  # 为了防止产生最高位进位，添加结点时指针丢失，用next
                if flag:
                    l2.val += 1
                    flag = False
                l2.val += l1.val
                if l2.val > 9:
                    l2.val -= 10
                    flag = True
                l1 = l1.next
                l2 = l2.next
            if flag:    # 如果向最高位进位
                l2.val += 1
                flag = False     
            l2.val += l1.val
            if l2.val > 9:
                l2.val -= 10
                flag = True
            if flag:    # 最高位向下一位进位（添加结点）
                l2.next = ListNode(1)
        else:   # l2长时
            while l1:   # 计算公共部分
                if flag:    
                    l2.val += 1
                flag = False
                l2.val += l1.val
                if l2.val > 9:
                    l2.val -= 10
                    flag = True
                l1 = l1.next
                l2 = l2.next
            while l2.next:  # 计算l2多余部分，同样，为了防止添加节点时指针丢失，用next
                if flag:
                    l2.val += 1
                flag = False
                if l2.val > 9:
                    l2.val -= 10
                    flag = True
                l2 = l2.next
            if flag:    # 向最高位进位
                l2.val += 1
                flag = False
                if l2.val > 9:
                    l2.val -= 10
                    flag = True
            if flag:    # 最高位向下一位进位
                l2.next = ListNode(1)
        return l3

2.2 我的改良

• 将最高位拿出来单独判断造成代码有过多的冗余
• 冗余是为了防止最高位向下一位产生进位时，指针成为None丢失而不能再添加结点的问题出现，采用l1.next和l2.next作为终止条件将最高位单独拿出来判断造成的
• 为了解决上述问题，引入滚动的指针p，使其始终指向l2所指向结点的前一个结点，就能避免指针的丢失
• 引入p之后，长度相等和不等两种情况下公共部分代码的相加可以合并
• 公共部分加法完成之后，判断l2是否有剩余
• 最后判断最高位是否产生进位

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def getLength(l):   # 计算单链表长度
    length = 0
    if not l:
        return 0
    else:
        while l:
            length += 1
            l = l.next
        return length
        
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        length1 = getLength(l1)
        length2 = getLength(l2)
        flag = False
        if length1 > length2:   # 保持l2为长链表
            l3 = l1
            l1 = l2
            l2 = l3

        l3 = l2     # 直接在l2上相加，l3指向l2
        while l1:  # 公共部分相加
            if flag:
                l2.val += 1
                flag = False
            l2.val += l1.val
            if l2.val > 9:
                l2.val -= 10
                flag = True
            l1 = l1.next
            p = l2
            l2 = l2.next
        while l2:   # 当l2有剩余时
            if flag:
                l2.val += 1
                flag = False
            if l2.val > 9:
                l2.val -= 10
                flag = True
            p = l2
            l2 = l2.next
        if flag:    # 当最高位向后一位进位时（需要添加节点时）
            p.next = ListNode(1)
        return l3

3.官方解法

• 充分利用了python的语言特性
• 不用考虑两个数的长度，可以将不等长转换为等长进行解决

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(l1.val+l2.val)	# 建立结果列表
        cur = head	# 滚动指针
        while l1.next or l2.next:	# 当加法没有结束时
            l1 = l1.next if l1.next else ListNode()		# 遍历结束添加结点（根据结点定义默认为0）
            l2 = l2.next if l2.next else ListNode()
            cur.next = ListNode(l1.val + l2.val + cur.val // 10)	# 建立新结点，本位值相加+前一位的进位
            cur.val = cur.val % 10	# 原结点取余
            cur = cur.next	# 指针滚动
        if cur.val >= 10:	# 当最高位产生进位时
            cur.next = ListNode(cur.val // 10)	# 添加新结点
            cur.val = cur.val % 10	# 本位取余
        return head