Java 计算链表中值的总和

Calculating the Sum of values in a linked list

提问by rtindru

I got a programming question at an interview recently.

我最近在面试中遇到了一个编程问题。

There are 2 linked lists. Each node stores a value from 1 through 9 (indicating one index of the number). Hence 123 would be a linked list 1->2->3

有2个链表。每个节点存储一个从 1 到 9 的值（表示数字的一个索引）。因此 123 将是一个链表 1->2->3

The task was to create a function:

任务是创建一个函数：

static LinkedListNode getSum(LinkedListNode a, LinkedListNode b)

static LinkedListNode getSum(LinkedListNode a, LinkedListNode b)

that would return the sum of the values in the 2 linked list arguements.

这将返回 2 个链表论证中的值的总和。

If the array a is: 1->2->3->4

如果数组a是：1->2->3->4

And the array b is: 5->6->7->8

而数组 b 是：5->6->7->8

The answer should be: 6->9->1->2

答案应该是：6->9->1->2

Here is my algorithm:

这是我的算法：

Go through each node in a and b, get the values as an integer and add them. Create a new linked list with the those values.

遍历 a 和 b 中的每个节点，获取整数形式的值并将它们相加。使用这些值创建一个新的链表。

Here is the code: It runs with a complexity of O(n) roughly I assume. Once through each of the array inputs and once to create the output array.

这是代码：我假设它以 O(n) 的复杂度运行。一次通过每个数组输入，一次创建输出数组。

Any improvements? Better algorithms... or code improvements

有什么改进吗？更好的算法……或代码改进

public class LinkedListNode {
        LinkedListNode next;
        int value;

    public LinkedListNode(int value) {
        this.value = value;
        this.next = null;
    }

    static int getValue(LinkedListNode node) {
        int value = node.value;
        while (node.next != null) {
            node = node.next;
            value = value * 10 + node.value;
        }
        return value;
    }

    static LinkedListNode getSum(LinkedListNode a, LinkedListNode b) {
        LinkedListNode answer = new LinkedListNode(0);
        LinkedListNode ans = answer;
        int aval = getValue(a);
        int bval = getValue(b);
        int result = aval + bval;
        while (result > 0) {
            int len = (int) Math.pow((double) 10,
                    (double) String.valueOf(result).length() - 1);
            int val = result / len;
            ans.next = new LinkedListNode(val);
            ans = ans.next;
            result = result - val*len;
            }    
        return answer.next;
    }
}

采纳答案by dkatzel

Other solutions I have seen for this problem involve building the returned list incrementally by iterating backwards over both the input lists at the same time adding each element as you go to a new list. That way is more complicated because you have to add each element and deal with carry overs.

对于这个问题，我看到的其他解决方案涉及通过向后迭代两个输入列表来增量构建返回的列表，同时在您转到新列表时添加每个元素。这种方式更复杂，因为您必须添加每个元素并处理结转。

If the array a is: 1->2->3->4

如果数组a是：1->2->3->4

And the array b is: 5->6->7->8

而数组 b 是：5->6->7->8

Iterate backwards

向后迭代

Then 4 + 8 = 12 (returned list current = 2)

然后 4 + 8 = 12（返回的列表当前 = 2）

carry the 1

携带 1

(1) + 3 + 7 = 11 (returned list = 1-> 2)

(1) + 3 + 7 = 11（返回列表 = 1-> 2）

carry the 1

携带 1

(1) + 2 + 6 = 9 (returned list = 9 -> 1 ->2 )

(1) + 2 + 6 = 9（返回列表 = 9 -> 1 ->2 ）

1 + 5 = 6 ( return list = 6->9>1->2)

1 + 5 = 6（返回列表 = 6->9>1->2）

You can implement this by using Stacks to get the LIFO nature to iterate backwards if the list is only singly linked.

如果列表只是单向链接，您可以通过使用堆栈来实现 LIFO 性质以向后迭代。

回答by dkatzel

Hi @rtindru: As you told that you want to add two linked list. The first linked list a is: 1->2->3->4The second linked list b is: 5->6->7->8

嗨@rtindru：正如您所说，您要添加两个链表。第一个链表 a 是：1->2->3->4第二个链表 b 是：5->6->7->8

In the question it is not mentioned that digits stored in the linked list is store in same order or reverse order as the number is appeared. First approach is more difficult.

在问题中没有提到存储在链表中的数字与数字出现的顺序相同或相反。第一种方法比较困难。

First Approach:

第一种方法：

list a: 1234
list b: 5678

The answer should be: 6->9->1->2

答案应该是： 6->9->1->2

   1 2 3 4
+  5 6 7 8
-----------------
   6 9 1 2

Second Approach

第二种方法

If number is stored in the reverse order then

如果数字以相反的顺序存储，则

First linked list a is: 1->2->3->4. Actual number: N1=4321. And the second linked list b is: 5->6->7->8. Actual number: N2=8765. Sum will be 6->8->0->3->1. This is the easy approach.

第一个链表 a 是：1->2->3->4。实际人数：N1=4321。第二个链表 b 是：5->6->7->8。实际人数：N2=8765。总和将是6->8->0->3->1。这是简单的方法。

In the question you are asking for First Approach and given example is also for first approach but your source code is for second approach. Please conform it.

在您要求第一种方法的问题中，给出的示例也适用于第一种方法，但您的源代码适用于第二种方法。请遵照。

回答by Shaohua Li

Other answers I saw often rely on an extra stack. Actually it can be solved with only O(1)extra space. I modified the example in another answer to make the two lists different in length:

我看到的其他答案通常依赖于额外的堆栈。实际上它可以只用O(1)额外的空间来解决。我修改了另一个答案中的示例，使两个列表的长度不同：

list a is: 1->2->3->4
list b is: 5->6->7->8->3->6

We can just iterate both lists, store the values of the current values in aand b, in the value of the new list c. But we cannot simply take the sum of the two values as the value in c, because in case the two lists are different in length, we couldn't recover the original values in list aand b. A little trick is to generate a two-digit value, the first digit being the value in a, and the second the value in b, like:

我们可以只迭代两个列表，将当前值的值存储在a和 中b，在新列表的值中c。但是我们不能简单地将两个值的总和作为 中的值c，因为如果两个列表的长度不同，我们将无法恢复列表a和 中的原始值b。一个小技巧是生成一个两位数的值，第一个数字是 中的值a，第二个数字是 中的值b，例如：

list c: 15 <- 26 <- 37 <- 48 <- 3 <- 6
                                     ^ pointer "p1"
                           ^ pointer "p2" here to mark the end of list a

Once list cis fully created, we rewind from pointer "p1". We first separate the two numbers in the node at pointer "p2", then add the right number to the value at p1. Then we reverse p1 and set p1->next, and p2 and p2->next, and then proceed to the previous nodes.

一旦列表c完全创建，我们从指针“p1”开始倒带。我们首先将指针“p2”处的节点中的两个数字分开，然后将正确的数字与 p1 处的值相加。然后我们反转 p1 和 set p1->next，以及 p2 和p2->next，然后继续到前面的节点。

list c: 15 <- 26 <- 37 <- 8 <- 3 -> 4
                               ^ p1
                     ^ p2
                               carry = 1

The time complexity is 2*max( length(a), length(b) ).

时间复杂度为2*max( length(a), length(b) )。

回答by Ankit

Here's my answer to this question (used C# instead of Java but the logic can be replicated easily in either language). I used linked list reversal for forward summing while for reverse storage, I used the carry forward approach.

这是我对这个问题的回答（使用 C# 而不是 Java，但逻辑可以很容易地用任何一种语言复制）。我使用链表反转进行前向求和，而对于反向存储，我使用结转方法。

/*  Program: Given two numbers represented in a linked list in reverse order, sum them and store the result in a third linked list
 *  
 *  Date: 12/25/2015
 */

using System;

namespace CrackingTheCodingInterview
{
    /// <summary>
    /// Singly Linked List with a method to add two numbers stored in two linked lists in reverse order
    /// </summary>
    public partial class SinglyLinkedList
    {
        /// <summary>
        /// Adding two numbers stored in a linked list in reverse order
        /// </summary>
        /// <param name="num1">Linked List 1 storing number 1</param>
        /// <param name="num2">Linked List 2 storing number 2</param>
        /// <param name="result">Linked List 3 storing sum of number 1 and number 2</param>
        public static void SumNumbersReverse(SinglyLinkedList num1, SinglyLinkedList num2, SinglyLinkedList result)
        {
            int carryForward = 0;
            int sum = 0;

            Node num1Digit = num1.head;
            Node num2Digit = num2.head;

            int sum1 = 0;
            int sum2 = 0;

            while (num1Digit != null || num2Digit != null)
            {
                if (num1Digit == null)
                {
                    sum1 = 0;
                }
                else
                {
                    sum1 = (int)num1Digit.Data;
                }

                if (num2Digit == null)
                {
                    sum2 = 0;
                }
                else
                {
                    sum2 = (int)num2Digit.Data;
                }

                sum = sum1 + sum2 + carryForward;

                if (sum > 9)
                {
                    carryForward = 1;
                }
                else
                {
                    carryForward = 0;
                }

                result.Insert(sum % 10);

                if (num1Digit != null)
                {
                    num1Digit = num1Digit.Next;
                }

                if (num2Digit != null)
                {
                    num2Digit = num2Digit.Next;
                }
            }

            result.ReverseList();
        }

        /// <summary>
        /// Adding two numbers stored in a linked list in reverse order
        /// </summary>
        /// <param name="num1">Linked List 1 storing number 1</param>
        /// <param name="num2">Linked List 2 storing number 2</param>
        /// <param name="result">Linked List 3 storing sum of number 1 and number 2</param>
        public static void SumNumbersForward(SinglyLinkedList num1, SinglyLinkedList num2, SinglyLinkedList result)
        {
            num1.ReverseList();
            num2.ReverseList();

            SumNumbersReverse(num1, num2, result);

            result.ReverseList();
        }

        /// <summary>
        /// Reverse a singly linked list
        /// </summary>
        public void ReverseList()
        {
            Node prev = null;
            Node curr = head;
            Node currNext;

            while(curr != null)
            {
                currNext = curr.Next;
                curr.Next = prev;
                prev = curr;
                curr = currNext;
            }

            head = prev;
        }
    }


    internal class SumNumbersLinkedListTest
    {
        static void Main()
        {
            SinglyLinkedList num1 = new SinglyLinkedList();
            SinglyLinkedList num2 = new SinglyLinkedList();

            num1.Insert(6);
            num1.Insert(1);
            num1.Insert(7);

            num2.Insert(2);
            num2.Insert(9);
            num2.Insert(5);

            num1.Print();
            num2.Print();

            SinglyLinkedList resultReverseSum = new SinglyLinkedList();
            SinglyLinkedList resultForwardSum = new SinglyLinkedList();

            SinglyLinkedList.SumNumbersReverse(num1, num2, resultReverseSum);
            Console.WriteLine("After summing reverse: ");
            resultReverseSum.Print();

            SinglyLinkedList num3 = new SinglyLinkedList();
            SinglyLinkedList num4 = new SinglyLinkedList();

            num3.Insert(7);
            num3.Insert(1);
            num3.Insert(6);

            num4.Insert(5);
            num4.Insert(9);
            num4.Insert(2);

            SinglyLinkedList.SumNumbersForward(num3, num4, resultForwardSum);
            Console.WriteLine("After summing forward: ");
            resultForwardSum.Print();

            Console.ReadLine();
        }
    }
}

回答by Aerin

You can do it by reversing the linkedlists. This is a c# implementation and it's O(n).

您可以通过反转链表来实现。这是 ac# 实现，它是 O(n)。

    public LinkedList ElementSum(LinkedList other)
    {
        LinkedList linkedListSum = new LinkedList();
        this.Reverse();
        other.Reverse();
        Node n1 = this.head, n2 = other.head;
        int toAdd = 0, carryOver = 0;
        while ((n1 != null) || (n2 != null))
        {
            int num1 = (int) (n1 == null ? 0 : n1.NodeContent);
            int num2 = (int) (n2 == null ? 0 : n2.NodeContent);
            toAdd = (num1 + num2 + carryOver) % 10;
            carryOver = (int)(num1 + num2 + carryOver) / 10;
            linkedListSum.Add(toAdd);
            n1 = (n1 == null ? null : n1.Next);
            n2 = (n2 == null ? null : n2.Next);
        }
        this.Reverse();
        other.Reverse();
        linkedListSum.Reverse();
        return linkedListSum;
    }