更多题解，请关注公众号：程序员学长，让你进大厂不走弯路

两个链表生成相加链表

问题描述

LeetCode 剑指 Offer II 025. 链表中的两数相加

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。给定两个这种链表，请生成代表两个整数相加值的结果链表。

示例：

输入：[9,3,7]，[6,3]

返回值：{1,0,0,0}

分析问题

由于两个数字相加是从个位数开始，然后再十位数、百位数。对于的链表中，我们需要将两个链表进行右端对齐，然后从右往左进行计算。

要想让两个链表右端对齐，我们有两种实现方式。

1. 将两个链表进行反转，然后直接求和。
2. 借助栈这种先进后出的特性，来实现链表的右端对齐。

我们先来看一下如何使用链表反转来实现。

class Solution(object):
    def reverse(self, head):
        cur = head
        #初始化时，pre为None
        pre = None
        while cur:
            next=cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre
    def addTwoNumbers(self, l1, l2):
        #将两个链表翻转
        l1 = self.reverse(l1)
        l2 = self.reverse(l2)
        head=ListNode(0)
        pre=head
        #代表是否进位
        carray=0
        while l1 or l2:
           v1=l1.val if l1 else 0
           v2=l2.val if l2 else 0
           sum=v1+v2+carray
           #进位数
           carray=int(sum/10)
           tmp=sum%10
           node=ListNode(tmp)
           pre.next=node
           pre=pre.next
           if l1:
               l1=l1.next
           if l2:
               l2=l2.next
        if carray==1:
            node=ListNode(carray)
            pre.next=node
        
        return self.reverse(head.next)

下面我们来看一下如何使用栈来求解。我们首先将两个链表从头到尾放入两个栈中，然后每次同时出栈，就可以实现链表的右端对齐相加，我们来看一下代码如何实现。

def addTwoNumbers(l1, l2):
    #申请两个栈
    stack1=[]
    stack2=[]
    #l1入栈
    while l1:
        stack1.append(l1.val)
        l1 = l1.next
    while l2:
        stack2.append(l2.val)
        l2 = l2.next

    head = None
    carry = 0

    while stack1 and stack2:
        num = stack1.pop() + stack2.pop() + carry
        #求进位数
        carry=int(num/10)
        tmp=num%10
        node = ListNode(tmp)
        node.next = head
        head = node


    s = stack1 if stack1 else stack2
    while s:
        num = s.pop() + carry
        carry = int(num / 10)
        tmp = num % 10
        node = ListNode(tmp)
        node.next = head
        head = node

    if carry==1:
        node = ListNode(carry)
        node.next = head
        head = node
    return head