javascript - JavaScript：遍历和反转单链表以及在 SLL 和数字之间进行转换

Question

简介 今天，在对 Facebook JavaScript 问题进行模拟面试时，我对如何处理单链表一无所知。到目前为止，我的代码只是一个函数，它接受 2 个链表并返回另一个链表。我的计划如下。

问题 给你两个代表两个非负整数的任意长度的非空链表。这些数字以相反的顺序存储，它们的每个节点都包含一个数字。将两个数字相加并将其作为链表返回。

您可以假设这两个数字不包含任何前导零，除了数字 0 本身。

例子：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 解释：342 + 465 = 807。

计划

1. 将第一个链表中的每个数字按顺序复制到一个数组中。
2. 反转数组。
3. 将数组转换为字符串，然后转换为整数并将其存储在变量中。
4. 对第二个链表重复此操作。
5. 将这两个数字相加并将该值存储在一个变量中。
6. 将此总和转换为字符串。
7. 在此字符串上使用 Array.from 将其转换为数组，然后反转数组。
8. ?
9. 返回新的链表。

/*
 * Definition for singly-linked list.
 * function ListNode(val)
 * {
 *  this.val = val;
 *  this.next = null;
 * }
 */

/* Expected input and output.
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */

var addTwoNumbers = function(l1, l2)
{

};

标签： javascript

Answer 1

在处理链表时，您可以轻松地采用递归方法。它倾向于保持代码简单。要将两个链表添加在一起，您需要做的就是：

1. 取一个节点
2. 将两个值相加
3. 将该值保存在新节点中。
4. 移动到下一个节点并从步骤 1 开始重复。

这是总纲。需要跟踪的边缘情况很少

• 两个数字的总和大于10- 在这种情况下，您必须将额外的数字带入下一个求和操作。因此，对于您的总和，12您只需要保留2并结转即可1。
• 一个列表已经用尽，但另一个列表仍然具有值 - 只是将其视为具有值0- 这不会影响结果。如果你尝试求和1，0你会得到1，这是正确的。
• 两个列表都已用尽，但有一个值结转 - 与上面相同。如果你对那些是9和的列表求和3，那么你会得到2，下一次迭代将没有更多的列表，而是1.

/*
 * Definition for singly-linked list.
 */
function ListNode(val)
{
  this.val = val;
  this.next = null;
}

/* Expected input and output.
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2)
{
  return recursivelyAddLists(l1, l2, 0);
};

/* 
 * Recursively add two lists together producing a new list for each digit
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @param {number} carryover 
 * @return {ListNode}
 */
function recursivelyAddLists(l1, l2, carryover)
{
  //you can also safely assume that the carryover is always present. 
  //But adding a default is a good practice
  carryover = carryover || 0;
  
  //if there is nothing to add, we are finished
  if (l1 == null && l2 == null && carryover === 0) return null;
  
  //provide fallback in case at least one or both lists are exhausted
  l1 = l1 || new ListNode(0);
  l2 = l2 || new ListNode(0);
  
  //calculate the sum of both nodes with any potential leftover from previous sums
  var sum = l1.val + l2.val + carryover;
  
  //clamp to only single digit numbers
  var newVal = sum % 10
  
  //the amount to move add with the next nodes
  var newCarryover = Math.floor(sum / 10);
  
  //create the result node
  var newList = new ListNode(newVal);
  
  //recursively determine what the next node is
  newList.next = recursivelyAddLists(l1.next, l2.next, newCarryover);
  
  //finish
  return newList
}


//use the sample data for a test
var input1 = new ListNode(2);
input1.next = new ListNode(4);
input1.next.next = new ListNode(3);

var input2 = new ListNode(5);
input2.next = new ListNode(6);
input2.next.next = new ListNode(4);

console.log(debugPrintList(addTwoNumbers(input1, input2)))


//simple function to recursively collect the content of the list to a string
function debugPrintList(list) {
  if (list.next == null) return list.val;
  return list.val + " -> " + debugPrintList(list.next);
}

我创建了一个新函数来进行递归加法，以保留第一个函数的接口。唯一的区别是carryover参数。但是，可以只添加参数并将其默认为零，并且仍然可以工作。但是，鉴于这是一次面试，他们可能会因为这种变化而惩罚你。尽管如此，为了完整起见，这看起来是这样的：

/*
 * Definition for singly-linked list.
 */
function ListNode(val)
{
  this.val = val;
  this.next = null;
}

/* Expected input and output.
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2, carryover) //<- adding the parameter
{
  carryover = carryover || 0;
  
  if (l1 == null && l2 == null && carryover === 0) return null;
  
  l1 = l1 || new ListNode(0);
  l2 = l2 || new ListNode(0);
  
  var sum = l1.val + l2.val + carryover;
  
  var newVal = sum % 10 
  var newCarryover = Math.floor(sum / 10);
  
  var newList = new ListNode(newVal);
  
  //recursively calling this same function
  newList.next = addTwoNumbers(l1.next, l2.next, newCarryover);
  
  return newList
};


//use the sample data for a test
var input1 = new ListNode(2);
input1.next = new ListNode(4);
input1.next.next = new ListNode(3);

var input2 = new ListNode(5);
input2.next = new ListNode(6);
input2.next.next = new ListNode(4);

console.log(debugPrintList(addTwoNumbers(input1, input2)))


//simple function to recursively collect the content of the list to a string
function debugPrintList(list) {
  if (list.next == null) return list.val;
  return list.val + " -> " + debugPrintList(list.next);
}

最后一点 - 此解决方案仅使用 ES5 功能。我基于给出的代码。ES6 不会真正产生大的影响，但最显着的变化是你不需要手动给一个默认值carryover- 相反你可以简单地拥有recursivelyAddLists(l1, l2, carryover = 0). 其他 ES6 更改充其量是次要的 - 使用letandconst代替var并且可能使用解构来获取节点和下一个节点的值，因此您可以执行类似的操作

const {val: value1 = 0, next: next1 = null} = l1 || {}
const {val: value2 = 0, next: next2 = null} = l2 || {}

但是，我个人认为可读性较差。