链表求和

难度:

标签:

题目描述

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

Example:

Input: (7 -> 1 -> 6) + (5 -> 9 -> 2). That is, 617 + 295.
Output: 2 -> 1 -> 9. That is, 912.

Follow Up: Suppose the digits are stored in forward order. Repeat the above problem.

Example:

Input: (6 -> 1 -> 7) + (2 -> 9 -> 5). That is, 617 + 295.
Output: 9 -> 1 -> 2. That is, 912.

代码结果

运行时间: 56 ms, 内存: 15.1 MB

/*
 * 使用Java Stream API实现对两个用链表表示的整数求和
 * 输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
 * 输出：2 -> 1 -> 9，即912
 */

import java.util.LinkedList;
import java.util.stream.IntStream;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class SolutionStream {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        LinkedList<Integer> stack1 = new LinkedList<>();
        LinkedList<Integer> stack2 = new LinkedList<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        int carry = 0;
        ListNode head = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int sum = (stack1.isEmpty() ? 0 : stack1.pop()) + (stack2.isEmpty() ? 0 : stack2.pop()) + carry;
            carry = sum / 10;
            ListNode newNode = new ListNode(sum % 10);
            newNode.next = head;
            head = newNode;
        }
        return head;
    }
}

解释

方法:

该题解采用了逐位相加的方法来处理两个链表表示的数字的加法。首先，创建一个哑节点(dummy node)作为新链表的头部，用于简化边界情况的处理。两个指针p1和p2分别遍历两个链表，同时一个变量carry用于存储进位。在每一步中，将p1和p2指向的节点的值（如果存在）和carry相加，计算得到的总和如果大于等于10，则设置进位carry为1，并将总和减去10；否则，进位carry设为0。然后创建一个新节点，其值为当前位的结果，并将其加到结果链表的末尾。遍历继续，直到两个链表都完全遍历完且没有进位。最后，返回哑节点的下一个节点，即结果链表的头节点。

时间复杂度:

O(max(m, n))

空间复杂度:

O(max(m, n))

代码细节讲解

🦆

在处理链表的逐位相加时，如果链表的长度不相等，此算法是如何确保没有遗漏任何数位的？

▷

在此算法中，通过使用两个指针分别遍历两个链表，即使链表长度不相等，也能确保处理所有节点。在循环中，只要任何一个链表的指针还未遍历完或存在未处理的进位（carry != 0），循环就会继续执行。如果某个链表已经遍历完，其对应的指针会指向null，此时该链表对应数位被视为0，确保加法可以继续进行，直至两个链表都完全遍历完且没有进位。

🦆

在题解中提到，如果两个链表完全遍历完毕后还存在进位，应该如何处理？是否需要添加额外的节点来表示这个进位？

▷

如果在两个链表都完全遍历完毕后还存在进位，根据算法设计，我们需要添加一个额外的节点来表示这个进位。最后一次循环中，如果计算后的进位（carry）不为0，算法会创建一个新的节点，其值为此时的进位值（通常是1），并将此节点添加到结果链表的末尾。这确保了最高位的进位也被正确记录在结果链表中。

🦆

为什么选择使用哑节点（dummy node）开始构建结果链表，而不是直接从第一个实际的节点开始？这样做有什么好处？

▷

使用哑节点开始构建结果链表的主要好处是简化了代码逻辑，避免了对头节点进行特殊处理。哑节点作为结果链表的初始节点，可以在不确定第一个节点值之前就建立链表结构，避免了在循环内部需要检查并特殊处理结果链表的头节点的情况。最后返回哑节点的下一个节点作为实际的头节点，从而使整个链表的处理更加统一和简洁。

🦆

在计算过程中，如果当前位的和没有超过10，直接清除进位（carry=0），这样的处理方式是否对所有情况都适用？

▷

是的，这样的处理方式对所有情况都适用。在每次循环中，将两个链表的相应数位和已有的进位值相加。如果这个总和小于10，则不需要进位，因此将进位（carry）设置为0。如果总和大于或等于10，则生成一个新的进位（通常设置为1），并调整当前位的数值（总和减10）。这样的逻辑确保了每一位的正确计算，同时进位也得到了正确的处理。

链表求和

题目描述

代码结果

解释

代码细节讲解

相关问题