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

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

你可能感兴趣的