369.Plus-One-Linked-List

369. Plus One Linked List

题目地址

题目描述

Given a non-negative integer represented as non-empty a singly linked list of digits, plus one to the integer.
You may assume the integer do not contain any leading zero, except the number 0 itself.
The digits are stored such that the most significant digit is at the head of the list.
Example :
Input: [1,2,3]
Output: [1,2,4]

代码

Approach #1 Sentinel Head

Time: O(N) && Space: O(1)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode plusOne(ListNode head) {
// sentinel head
ListNode sentinel = new ListNode(0);
sentinel.next = head;
ListNode notNine = sentinel;
// find the rightmost not-nine digit
while (head != null) {
if (head.val != 9) notNine = head;
head = head.next;
}
// increase thsi rightmost not-nine digit
notNine.val++;
notNine = notNine.next;
while (notNine != null) {
notNine.val = 0;
notNine = notNie.next;
}
return sentinel.val != 0 ? sentinel : sentinal.next;
}
}

Approach #2 Recursive DFS

class Solution {
public ListNode plusOne(ListNode head) {
if (DFS(head) == 0) {
return head;
} else {
ListNode newHead = new ListNode(1);
newHead.next = head;
return newHead;
}
}
private int DFS(ListNode head) {
if (head == null) return 1;
if (DFS(head.next) == 0) { // carry
return 0;
}
int val = head.val + 1;
head.val = val % 10;
return val / 10; // next carry
}
}