链表算法

两个链表相加

https://leetcode.com/problems/add-two-numbers/description/

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

const addTwoNumbers = function (l1, l2) {
  // 辅助函数：给定链表两个节点，和前一次的和，然后获取这一次的和 val，以及超出部分 next 
  const getVal = function (l1, l2, plus = 0) {
    const val1 = l1 && l1.val;
    const val2 = l2 && l2.val;
    const total = val1 + val2 + plus;
    return {
      val:total % 10,
      next: parseInt(total / 10),
    }
  }

  let l = null;
  let plus = 0;

  // 从后向前递归计算链表的节点
  function setNode(vm, l1, l2) {
    if(!l1 && !l2 && !plus) {
      return vm;
    }
    const totalObj = getVal(l1, l2, plus)

    // 当前节点计算和超过10，就累计到下一位中
    if (totalObj.next) {
      plus = totalObj.next;
    } else {
      plus = 0
    }

    // 如果链表后面有节点，那么继续加入后面的节点
    if(!l) {
      l = new ListNode(totalObj.val);
      vm = l;
    } else {
      vm.next = new ListNode(totalObj.val);
      vm = vm.next;
    }

    if( (l1 && l1.next) || (l2 && l2.next) || plus) {
      return setNode(vm, l1 && l1.next, l2 && l2.next)
    }
  }

  setNode(l, l1, l2)
  return l;
};

---

Last update: May 28, 2021