LeetCode刷题日志2两数相加

题目：传送门
类别：单向链表
难度：中等

容易想到的解法

一开始想的，先变数组，然后拼装成数字，直接相加，进位问题自然解决。后来发现，大数相加 js 会用科学计数法表示，不好再还原回链表，于是老老实实手动实现了进位。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {const arr1 = getArrFromLink(l1);
  const arr2 = getArrFromLink(l2);
  const arr3 = [];
  
  const len = Math.max(arr1.length, arr2.length);
  let flag = 0;
  
  for (let i = 0; i < len || flag; i += 1) {const byte1 = arr1[i] || 0;
    const byte2 = arr2[i] || 0;
    const byte3 = byte1 + byte2 + flag;
    if (byte3 >= 10) {arr3.push(byte3 - 10);
      flag = 1;
    } else {arr3.push(byte3);
      flag = 0;
    }
  }
  
  return getLinkFromArr(arr3);
};

function getArrFromLink(link) {const arr = [];
  let pointer = link;
  while(pointer) {arr.push(pointer.val);
    pointer = pointer.next;
  }
  return arr;
}
function getLinkFromArr(arr) {const link = {};
  let pointer = link;
  arr.forEach((item, index) => {
    pointer.val = item;
    if (index === arr.length - 1) {pointer.next = null;} else {pointer.next = {};
      pointer = pointer.next;
    }
  });
  
  return link;
}

最优解

既然都手动进位了，那还整数组干嘛，直接链表操作。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
  let pointer1 = l1;
  let pointer2 = l2;
  let flag = 0;
  
  while(typeof pointer1.val === 'number' || typeof pointer2.val === 'number' || flag) {if (pointer1.val === undefined) {pointer1.val = 0;}
    if (pointer2.val === undefined) {pointer2.val = 0;}
    
    pointer1.val = pointer1.val + pointer2.val + flag;
    if (pointer1.val >= 10) {
      pointer1.val = pointer1.val - 10;
      flag = 1;
    } else {flag = 0;}
    
    if (!pointer1.next && !pointer2.next && !flag) {return l1;}
    
    if (!pointer1.next) {pointer1.next = {};
    }
    pointer1 = pointer1.next;
    if (!pointer2.next) {pointer2.next = {};
    }
    pointer2 = pointer2.next;
  }
  
  return l1;
};

实际测试发现，两个方法内存和时间开销，后者都略优于前者。