[LeetCode] 369. Plus One Linked List

Given a non-negative integer represented as a 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 1:

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。这个整数的各个数位按照高位在链表头部、低位在链表尾部的顺序排列。

这个题有多种思路，我这里给出的是双指针的解法。思路是创建一个dummy节点，还是连到head之前（dummy.next = head）。此时再创建两个指针 i 和 j ，也都从dummy的位置开始往后走。j 只做一件事，就是看整个list里面是否有9，若遍历到当前位置不是9的话，也将i移动到该位置，直到j遍历完整个list。此时 i 停下的地方只会是两种情况

list的最后一个节点，此时只要对这个数字+1即可
如果最后一个节点是9的话，i停下的位置会在9之前的一个节点。比如[1, 2, 9]好了，i会停在2的位置。

第一种情况很好处理；第二种情况，因为i停下的位置是在2，所以只要把2变成3，将剩下的digits全部改为0即可。注意一个corner case是如果只有一个digit怎么办，这也就是为什么指针i 和 j 都从 dummy 开始而不是从 dummy.next 开始遍历的原因。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public ListNode plusOne(ListNode head) {
 3         ListNode dummy = new ListNode(0);
 4         dummy.next = head;
 5         ListNode i = dummy;
 6         ListNode j = dummy;
 7         while (j.next != null) {
 8             j = j.next;
 9             if (j.val != 9) {
10                 i = j;
11             }
12         }
13         i.val++;
14         i = i.next;
15         while (i != null) {
16             i.val = 0;
17             i = i.next;
18         }
19         if (dummy.val == 0) {
20             return dummy.next;
21         }
22         return dummy;
23     }
24 }

JavaScript实现

 1 /**
 2  * Definition for singly-linked list.
 3  * function ListNode(val) {
 4  *     this.val = val;
 5  *     this.next = null;
 6  * }
 7  */
 8 /**
 9  * @param {ListNode} head
10  * @return {ListNode}
11  */
12 var plusOne = function(head) {
13     let dummy = new ListNode(0);
14     dummy.next = head;
15     let i = dummy;
16     let j = dummy;
17     while (j.next !== null) {
18         j = j.next;
19         if (j.val !== 9) {
20             i = j;
21         }
22     }
23 
24     // i is the last non-9 digit
25     i.val++;
26     i = i.next;
27     while (i !== null) {
28         i.val = 0;
29         i = i.next;
30     }
31     return dummy.val === 0 ? dummy.next : dummy;
32 };

LeetCode 题目总结