当前位置: 面试刷题>> 两数相加(经典算法150题)


题目描述

给定两个非空链表,表示两个非负整数。这两个整数是逆序存储的,每个节点包含一个数字。将这两个数相加,并以相同的方式(逆序存储)返回一个新的链表。

示例

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807

注意

  • 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
  • 进位需要保留,例如输入为 (1 -> 2 -> 3) + (4 -> 5 -> 6) 时,输出应为 (5 -> 7 -> 9),而不是 (5 -> 7 -> 9 -> 0),因为结果不需要额外的零来填充。

PHP 代码示例

class ListNode {
    public $val = 0;
    public $next = null;

    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function addTwoNumbers($l1, $l2) {
    $dummy = new ListNode(0); // 创建一个哑节点
    $current = $dummy; // 当前节点指针
    $carry = 0; // 进位

    while ($l1 !== null || $l2 !== null || $carry > 0) {
        $x = ($l1 !== null) ? $l1->val : 0;
        $y = ($l2 !== null) ? $l2->val : 0;
        $sum = $x + $y + $carry;
        
        $carry = intval($sum / 10); // 计算进位
        $current->next = new ListNode($sum % 10); // 创建新节点存储当前位的和
        $current = $current->next; // 移动当前节点指针

        if ($l1 !== null) {
            $l1 = $l1->next;
        }
        if ($l2 !== null) {
            $l2 = $l2->next;
        }
    }

    return $dummy->next; // 返回哑节点的下一个节点作为结果链表的头节点
}

Python 代码示例

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1, l2):
    dummy = ListNode(0)
    current = dummy
    carry = 0

    while l1 or l2 or carry:
        x = l1.val if l1 else 0
        y = l2.val if l2 else 0
        sum = x + y + carry
        
        carry = sum // 10
        current.next = ListNode(sum % 10)
        current = current.next
        
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    return dummy.next

JavaScript 代码示例

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

function addTwoNumbers(l1, l2) {
    let dummy = new ListNode(0);
    let current = dummy;
    let carry = 0;

    while (l1 !== null || l2 !== null || carry > 0) {
        let x = (l1 !== null) ? l1.val : 0;
        let y = (l2 !== null) ? l2.val : 0;
        let sum = x + y + carry;
        
        carry = Math.floor(sum / 10);
        current.next = new ListNode(sum % 10);
        current = current.next;
        
        if (l1 !== null) {
            l1 = l1.next;
        }
        if (l2 !== null) {
            l2 = l2.next;
        }
    }

    return dummy.next;
}

以上代码均实现了题目要求的功能,即将两个逆序存储的链表表示的非负整数相加,并以逆序链表的形式返回结果。

推荐面试题