369 Plus One Linked List
369. Plus One Linked List
1. Question
Given a non-negative integer represented asnon-emptya 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
2. Implementation
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode plusOne(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode lastNotNine = dummy, curNode = head;
while (curNode != null) {
if (curNode.val != 9) {
lastNotNine = curNode;
}
curNode = curNode.next;
}
lastNotNine.val += 1;
curNode = lastNotNine.next;
while (curNode != null) {
curNode.val = 0;
curNode = curNode.next;
}
return dummy.val == 1 ? dummy : dummy.next;
}
}
3. Time & Space Complexity
时间复杂度: O(n), 空间复杂度: O(1)
Last updated
Was this helpful?