369. 给单链表加一 🔒

🟠   🔖  链表 数学  🔗 力扣 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;
};