陈恒承

两数之和

题目如下: 1l,l2 链表结构，要求存放在链表的节点相加

l1: 1-2->3
l2: 1->2->3
输出: 2->3->6;

l1: 1->7->3
l2: 2->3->1

输出 : 3->0->5

先说思路，我们自然要遍历我们的 l1,l2,了，但如何遍历呢？指针迭代法（while），递归法（浪费空间）。
一般而言，都是采用指针迭代法。下面根据实现的代码，作注释讲解。

function addNums(l1, l2) {
  let header = null,
    last = null;
  let carry = 0; // 进制

  while (l1 || l2) {
    /*
         为什么这么写呢？是因为 使每个位都一一对应上
         0 0 2
         0 5 0
      */
    let n1 = l1.val || 0;
    let n2 = l2.val || 0;

    let sum = n1 + n2 + carry;

    if (!header) {
      // 初始化..header,last ,last 的实质就是一个移动的指针
      header = last = new NodeList(sum % 10);
    } else {
      /*
        这一步很精妙，不断的自循环引用，产生下一级
      */
      last.next = new NodeList(sum % 10);
      /*这一步最关键，把指针指回新产生的对象，为了产生链*/
      last = last.next;
    }
    if (l1) {
      l1 = l1.next;
    }
    if (l2) {
      l2 = l2.next;
    }
    carry = sum > 10 ? 1 : 0;
  }

  if (carry > 0) {
    last.next = new NodeList(1);
  }
  // 我们的头，一直有了最开始的引用。
  return header;
}

总结

var addTwoNumbers = function (l1, l2) {
  let result = {};
  recursion(l1, l2, result, 0);
  //    console.log(result);

  return result;
};

function recursion(l1, l2, obj, isOverTen) {
  obj.next = {};

  if (l1 && l2) {
    // 接受上一次传过来的进制
    obj.val = l1.val + l2.val + (isOverTen ? 1 : 0);
    // 如果大于时，则处理-10。
    let isOver = obj.val > 9;
    obj.val = isOver ? obj.val - 10 : obj.val;

    if (l1.next !== null && l2.next !== null) {
    }

    recursion(l1.next, l2.next, obj.next, isOver);
  }

  //    if(l1.next!=null&&l2.next==null){
  //        obj.val=l1.val+isOverTen?1:0;
  //        recursion(l1.next,l2.next,obj.next,isOverTen);
  //    }

  //    if(l1.next===null&&l2.next!==null){
  //         obj.val=l2.val+isOverTen?1:0;
  //        recursion(l1.next,l2.next,obj.next,isOverTen);
  //    }

  if (l1 === null && l2 === null) {
    if (isOverTen) {
      obj.val = l;
    }
    obj.next = undefined;
  }
}

我一开始用的递归法，但能力有限，构造不出想要的链结构,没有找对递归的终止条件。对于链表，还是使用指针的方式最为稳妥，一个指针不够。我们可以用两个，甚至三个。如何构造一个链表呢，借助一个头尾节点，创建新的尾节点的时候，要不断改变 last 的指向，使 last 是指向 最新节点，这样才能构建一个链。