369. Plus One Linked List

🟠   🔖  链表 数学  🔗 LeetCode

题目

Given a non-negative integer represented as non-empty a singly linked list of digits, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list.

Example:

Input: head = [1,2,3]

Output: [1,2,4]

Example 2:

Input: head = [0]

Output: [1]

Constraints:

• The number of nodes in the linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• The number represented by the linked list does not contain leading zeros except for the zero itself.

题目大意

用一个 非空 单链表来表示一个非负整数，然后将这个整数加一。

你可以假设这个整数除了 0 本身，没有任何前导的 0。

这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。

解题思路

1. 反转链表。
2. 从链表头部开始遍历，逐位进行加一操作，处理进位。
3. 将链表再次反转，得到最终结果。

代码

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var plusOne = function (head) {
  // 1. 反转链表
  let reversedHead = reverse(head);
  let cur = reversedHead;
  let carry = 1;

  // 2. 遍历链表，对每个节点加一并处理进位
  while (cur && carry > 0) {
    let sum = cur.val + carry;
    cur.val = sum % 10; // 更新当前节点的值
    carry = Math.floor(sum / 10); // 计算进位
    if (cur.next) {
      cur = cur.next;
    } else if (carry > 0) {
      // 处理最高位的进位
      cur.next = new ListNode(carry);
      break;
    }
  }

  // 3. 再次反转链表得到结果
  return reverse(reversedHead);
};

var reverse = function (head) {
  let prev = null;
  let cur = head;
  while (cur) {
    let next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
};