6

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

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

任务是创建一个函数:

static LinkedListNode getSum(LinkedListNode a, LinkedListNode b)

这将返回 2 个链表参数中的值的总和。

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

数组 b 为:5->6->7->8

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

这是我的算法:

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

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

有什么改进吗?更好的算法......或代码改进

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;
    }
}
4

5 回答 5

3

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

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

数组 b 为:5->6->7->8

向后迭代

然后 4 + 8 = 12(返回列表当前 = 2)

携带 1

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

携带 1

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

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

如果列表只是单链接的,您可以通过使用堆栈来实现后进先出特性以向后迭代。

于 2013-10-11T14:33:56.903 回答
0

@rtindru:正如你所说,你想添加两个链表。第一个链表 a 是:1->2->3->4 第二个链表 b 是:5->6->7->8

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

第一种方法:

list a: 1234
list b: 5678

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

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

第二种方法

如果 number 以相反的顺序存储,则

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

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

于 2014-06-09T17:53:11.917 回答
0

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

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

我们可以迭代两个列表,将当前值的值存储在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

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

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

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

于 2015-03-11T05:30:33.007 回答
0

这是我对这个问题的回答(使用 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();
        }
    }
}
于 2015-12-25T22:52:17.520 回答
0

您可以通过反转链表来做到这一点。这是 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;
    }
于 2017-03-29T20:51:31.117 回答