我最近在一次面试中遇到了一个编程问题。
有 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;
}
}
我看到的针对此问题的其他解决方案涉及通过向后迭代两个输入列表来增量构建返回的列表，同时在转到新列表时添加每个元素。 这种方式更复杂，因为您必须添加每个元素并处理结转。
如果数组 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(
如果列表仅单向链接，则可以通过使用堆栈来实现这一点，以使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
{
/// <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();
}
}
}
您可以通过反转链接列表来做到这一点。这是一个 c# 实现和它是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;
}