JavaScript：遍历和反转单链表，并在SLL和数字之间进行转换

Question

今天，在做一个关于Facebook JavaScript问题的模拟采访时，我忽略了如何处理单链接列表。到目前为止，我的代码只是一个函数，它接受两个链表并返回另一个链表。我的计划在下面。

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

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

示例：

输入：（2-

计划

1. 按顺序将第一个链表中的每个数字复制到数组中
2. 反转阵列
3. 将数组转换为字符串，然后转换为整数，并将其存储在变量中
4. 对第二个链表重复此操作
5. 将两个数字相加并将此值存储在变量中
6. 将此总和转换为字符串
7. 使用数组。从该字符串开始，将其转换为数组，然后反转数组
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)
{

};

Answer 1

完成计划第8步的一种方法是使用数组的减少方法。

这样地：

function ListNode(val)
{
   this.val = val;
   this.next = null;
}

const array2List = function(list, nextValue)
{
   let node = new ListNode(parseInt(nextValue));
   node.next = list;

   return node;
}

let numberArray = Array.from('807');

let list = numberArray.reduce(array2List, null);

console.log(list);

或者改变你的计划，做一些类似的事情：

const addTwoNumbers = function(l1, l2)
{
   let sumList = new ListNode(0);
   let node    = sumList;
   let carry   = 0;

   while (node)
   {
      let l1Value = (l1) ? parseInt(l1.val) : 0;
      let l2Value = (l2) ? parseInt(l2.val) : 0;

      let sum  = carry + l1Value + l2Value;

      node.val = sum % 10;
      carry    = (sum - node.val)/10;

      if (l1) { l1 = l1.next }
      if (l2) { l2 = l2.next }

      node.next = (l1 || l2 || carry) ? new ListNode(0) : null;
      node      = node.next;
   }

   return sumList;
}

Answer 2

您不必创建包含与链表相同数据的新数组。您可以在迭代这两个列表并在同一循环中创建结果列表的同时处理这两个列表。在进行此操作时，您必须注意从加法器中进行的进位。

基本上你必须这样做：

let currNodeList1 = l1, currNodeList2 = l2;  //assuming that l1 and l2 point to head of linked list 
let resultListHead = null, currNodeResultList = null;  //to store the result
let carry = 0, sum = 0;
while(currNodeList1 != null && currNodeList2 != null) {
    sum = carry + currNodeList1.val + currNodeList2.val;
    carry = Math.trunc(sum / 10);   
    sum = sum % 10;

    let newListNode = new ListNode(sum);
    if(currNodeResultList == null) {
        resultListHead = newListNode;
    } else {
        currNodeResultList.next = newListNode;
    }
    currNodeResultList = newListNode;
    currNodeList1 = currNodeList1.next;
    currNodeList2 = currNodeList2.next;
}

if(currNodeList1 == null) {   //other list is longer in length
    while(currNodeList2 != null) {
         // calculate sum as carry + currNodeList2.val
         //same carry logic and keep appending to the end of the result list
    }
}

if(currNodeList2 == null) {   //other list is longer in length
    while(currNodeList1 != null) {
         //calculate sum as carry + currNodeList2.val
         //same carry logic and keep appending to the end of the result list
    }
}

显然，您可以通过重构重复的部分来使代码更加模块化，但总的想法应该是这样。

Answer 3

在处理链表时，可以轻松地采用递归方法。它倾向于保持代码简单。要将两个链接列表添加到一起，只需执行以下操作：

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