Leetcode 445.两数相加 II

题目详情

两数相加 II

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

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

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

输入：l1 = [0], l2 = [0]
输出：[0]

解题思路

本题需要逆向运算，因此容易想到栈的性质后进来的先出，这和我之前20题的讲的栈是一样的,建立a和b两个栈

从示例1开始，依次把数字放进去

先弹出3和4 3+4=7 新链表第一哥节点为7

再到6+4=10 这时出现两位数了 我们要进1位 然后取除10的余数为当前的节点

因此节点第二位是0

再到5+2=7 但别忘了之前的进位 所以是 5+2+1=8 第三个节点为8

这里b栈的数字已经全部用完了 这里取出来的数为0 所以是7+0 =7

最后一个节点为5

到这里还没完 因为题目要求是翻转的链表 因此我们再把链表反转一下即可

那现在开始写代码吧

先把数字放进去栈

a = []
b = []
while l1 or l2:
    if l1:
       a.append(l1.val)
       l1 = l1.next
            
    if l2:
       b.append(l2.val)
       l2 = l2.next

然后写个条件循环

出栈并处理进位添加节点

m = n = ListNode(0)
while a or b:
    if a:
       k = a.pop()
    else:
       k = 0
            
    if b:
        v = b.pop()
    else:
        v = 0
            
    s = (k+v+c)
    c = s // 10
    m.next = ListNode(s % 10)
    m = m.next

补位 (如果遍历完了 还有进位 则需补位)

if c:
   m.next = ListNode(c)

再写个反转链表的函数

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, curr = None, head
        while curr is not None:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        return prev

大功告成

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, curr = None, head
        while curr is not None:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        return prev

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        a = []
        b = []
        c = 0
        m = n = ListNode(0)
        k = 0
        v = 0
        while l1 or l2:
            if l1:
                a.append(l1.val)
                l1 = l1.next
            
            if l2:
                b.append(l2.val)
                l2 = l2.next 
        while a or b:
            if a:
                k = a.pop()
            else:
                k = 0
            
            if b:
                v = b.pop()
            else:
                v = 0
            
            s = (k+v+c)
            c = s // 10
            m.next = ListNode(s % 10)
            m = m.next
        if c:
            m.next = ListNode(c)
        return self.reverseList(n.next)

示例代码

Python3

## 时间复杂度: O(max(n,m))
## 空间复杂度: O(m+n)
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, curr = None, head
        while curr is not None:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        return prev

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        a = []
        b = []
        c = 0
        m = n = ListNode(0)
        k = 0
        v = 0
        while l1 or l2:
            if l1:
                a.append(l1.val)
                l1 = l1.next
            
            if l2:
                b.append(l2.val)
                l2 = l2.next 
        while a or b:
            if a:
                k = a.pop()
            else:
                k = 0
            
            if b:
                v = b.pop()
            else:
                v = 0
            
            s = (k+v+c)
            c = s // 10
            m.next = ListNode(s % 10)
            m = m.next
        if c:
            m.next = ListNode(c)
        return self.reverseList(n.next)

C++

// 时间复杂度: O(max(m,n))
// 空间复杂度: O(m+n)
// 本代码来自官方题解
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2;
        while (l1) {
            s1.push(l1 -> val);
            l1 = l1 -> next;
        }
        while (l2) {
            s2.push(l2 -> val);
            l2 = l2 -> next;
        }
        int carry = 0;
        ListNode* ans = nullptr;
        while (!s1.empty() or !s2.empty() or carry != 0) {
            int a = s1.empty() ? 0 : s1.top();
            int b = s2.empty() ? 0 : s2.top();
            if (!s1.empty()) s1.pop();
            if (!s2.empty()) s2.pop();
            int cur = a + b + carry;
            carry = cur / 10;
            cur %= 10;
            auto curnode = new ListNode(cur);
            curnode -> next = ans;
            ans = curnode;
        }
        return ans;
    }
};

PHP

// 时间复杂度: O(max(m,n))
// 空间复杂度: O(m+n)
// 本代码来自 https://leetcode.cn/problems/add-two-numbers-ii/solution/phpjian-ji-jie-fa-by-mek1986/
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {

    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2) {
        $num1='';//链表1表示的数字
        $num2='';//链表2表示的数字
        while($l1!=null){
            $num1.=$l1->val;
            $l1=$l1->next;
        }

        while($l2!=null){
            $num2.=$l2->val;
            $l2=$l2->next;
        }

        $sum=bcadd($num1,$num2,0);//求和,得到结果字符串
        $newList=null;
        $len=strlen($sum);        
        for($i=0;$i<$len;$i++){//循环结果字符串，就可以构建出链表
            if($newList==null){
                $newList=new ListNode($sum[$i]);
                $head=$newList;
            }else{
                $newList->next=new ListNode($sum[$i]);
                $newList=$newList->next;
            }
        }
        return $head;
    }
}

感谢收看