计算链表中的值的总和
我最近在接受采访时得到了编程问题。
有2个链接列表。 每个节点存储1到9的值（表示数字的一个索引）。 因此123将是链接列表1-> 2-> 3
任务是创建一个函数：
static LinkedListNode getSum(LinkedListNode a, LinkedListNode b)
这将返回2个链表列表中的值的总和。
如果arraysa是：1-> 2-> 3-> 4
并且arraysb是：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; } }
我在这个问题上看到的其他解决方案涉及通过在输入列表上向后迭代来逐步构建返回的列表，同时在转到新列表时添加每个元素。 这种方式更复杂，因为你必须添加每个元素并处理结转。
如果arraysa是：1-> 2-> 3-> 4
并且arraysb是：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）
如果列表仅单独链接，您可以通过使用Stacks来实现此操作以使LIFO性质向后迭代。
我看到的其他答案通常依赖额外的堆栈。 实际上它只能用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并设置p1->next ，p2和p2->next ，然后继续前面的节点。
list c: 15 <- 26 <- 37 <- 8 <- 3 -> 4 ^ p1 ^ p2 carry = 1
时间复杂度是2*max( length(a), length(b) ) 。
嗨@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
第二种方法
如果数字以相反的顺序存储
第一个链表a是： 1->2->3->4 。 实际数量： N1=4321 。 第二个链表b是： 5->6->7->8 。 实际数量： N2=8765 。 总和将是6->8->0->3->1 。 这是一种简单的方法。
在你要求第一种方法的问题中，给出的例子也是第一种方法，但你的源代码是第二种方法。 请遵守它。
这是我对这个问题的回答（使用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 { /// /// Singly Linked List with a method to add two numbers stored in two linked lists in reverse order /// public partial class SinglyLinkedList { /// /// Adding two numbers stored in a linked list in reverse order /// /// Linked List 1 storing number 1 /// Linked List 2 storing number 2 /// Linked List 3 storing sum of number 1 and number 2 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(); } /// /// Adding two numbers stored in a linked list in reverse order /// /// Linked List 1 storing number 1 /// Linked List 2 storing number 2 /// Linked List 3 storing sum of number 1 and number 2 public static void SumNumbersForward(SinglyLinkedList num1, SinglyLinkedList num2, SinglyLinkedList result) { num1.ReverseList(); num2.ReverseList(); SumNumbersReverse(num1, num2, result); result.ReverseList(); } /// /// Reverse a singly linked list /// 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(); } } }
您可以通过反转链接列表来完成此操作。 这是ac＃implementation，它是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; }