兩數相加

leetcode題目地址

解題源碼及測試

題目

給你兩個非空的鏈表，表示兩個非負的整數。它們每位數字都是按照逆序的方式存儲的，並且每個節點只能存儲一位數字。

請你將兩個數相加，並以相同形式返回一個表示和的鏈表。

你可以假設除了數字 0 之外，這兩個數都不會以 0  開頭。

• 示例 1：

輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[7,0,8]
解釋：342 + 465 = 807.

• 示例 2：

輸入：l1 = [0], l2 = [0]
輸出：[0]

• 示例 3：

輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出：[8,9,9,9,0,0,0,1]

提示：

• 每個鏈表中的節點數在範圍 [1, 100] 內
• 0 <= Node.val <= 9
• 題目數據保證列表表示的數字不含前導零

解答

遍歷兩個兩個鏈表，有值取值，無值取 0；由於一個節點只保存一位數字，因此不會>10；

因此只有兩種情況，>=10時進位，<10直接賦值；這裏用一個變量去記錄是否有進位，如果有，下一次計算時+1，這裏直接用Number(flag)的形式偷了個懶。

移動 move 指針，並對 next 創建 ListNode 節點；這裏需要判斷是否新增最後一個節點。當最後兩個節點數相加沒有進位時，不需要增加，>10時才增加，此時 val = 1。

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

export function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  let sum = 0;
  const result = new ListNode(0, null);
  let move = result;
  let flag = false;

  while (l1 || l2) {
    sum = (l1?.val ?? 0) + (l2?.val ?? 0) + Number(flag);
    if (sum >= 10) {
      move.val = sum % 10;
      flag = true;
    } else {
      move.val = sum;
      flag = false;
    }
    l1 && (l1 = l1.next);
    l2 && (l2 = l2.next);
    if (l1 || l2 || flag) {
      move = move.next = new ListNode(Number(flag), null);
    }
  }

  return result;
}