两数相加

链表的定义和分类

单链表

自定义链表节点
function ListNode(val,next){
  this.val = (val===undifined ? 0 : val)
  this.next = (next === undefined ? 0 : val)
}

class ListNode{
  val;
  next = null;
  constructor(value){
    this.val = value;
    this.next = null
  }
}

class ListNode{
  public val : number;
  public next : ListNode|null = null
  constructor(value:number){
    this.val = value;
    this.next = null;
  }
}

双链表

循环链表

链表相关题目

两数相加

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

var addTwoNumbers = function(l1, l2) {
// 首先新建一个节点
  let res = new ListNode(0)
  // 将节点赋值给变量curr，最终返回res.next就是链表的头，
  // p和q分别是第一个和第二个链表的头
  let curr = res, p = l1, q = l2
  //进位的时候需要的carry
  let carry = 0
  //循环终止的条件是两个链表元素都被遍历完
  while(p != null || q != null){
    // 将长度较短的链表后面补0，直到达到较长链表的长度
    let x = (p === null) ? 0 : p.val
    let y = (q === null) ? 0 : q.val
    // 求对应位置两数的和
    let sum = x + y + carry
    // 和大于0说明需要进位，进位数为sum/2
    carry = Math.floor(sum/10)
    // 保存在链表中的应该是余数，且应该创建一个ListNode
    curr.next = new ListNode(sum%10)
    // 让curr指向curr.next
    curr = curr.next
    // p和q都指向下一个结点
    if (p != null) p = p.next
    if (q != null) q = q.next
  }
  // 最后有可能出现两数的和的长度大于两数最长的哪个数的位数
  if (carry > 0){
    curr.next = new ListNode(carry)
  }
  return res.next
};