700053. Add 1 to a Linked List Number
Add 1 to a Linked List Number
Summary
Given a number represented as a linked list, add 1 to it. The number is represented in reverse order (i.e., units digit first). For example, if the input is 7 -> 1 -> 2, the output should be 8 -> 1 -> 2. This problem involves manipulating a linked list and performing arithmetic operations.
Detailed Explanation
The key to solving this problem is to understand that adding 1 to a number represented as a linked list is similar to adding 1 to an integer. We can start by checking the last node of the linked list, which represents the units digit of the number. If it's 9, we need to carry the 1 to the next node (which would be the tens place), and reset the current node to 0.
We continue this process until we reach the beginning of the linked list or until there is no more carrying needed. Here's a step-by-step breakdown:
- Start at the end of the linked list.
- If the current node is 9, carry the 1 to the next node and reset the current node to 0.
- If there are more nodes left in the list, move to the next node.
- Repeat steps 2-3 until you reach the beginning of the list or until there is no more carrying needed.
Time Complexity
The time complexity of this algorithm is O(n), where n is the number of digits in the input linked list. This is because we need to iterate through each node in the linked list once.
Space Complexity
The space complexity is O(1) as we are not using any additional space that scales with the size of the input.
Optimized Solutions
Java
public ListNode addOne(ListNode head) {
if (head == null) return new ListNode(1);
ListNode curr = head;
while (curr.next != null) {
curr = curr.next;
}
if (curr.val == 9) {
curr.val = 0;
head = addOne(head);
} else {
curr.val++;
}
return head;
}