Add One to a Number Stored in a Linked List
Updated
Problem statement
A whole number that is 0 or larger is stored in a singly linked list, one digit per node, with the most significant digit first. For example, the list [4,0,7] stores the number 407.
Given head, the first node of the list, add 1 to the number and return the first node of a list that stores the result in the same way.
The number has no leading zeros, so the first node is never 0 unless the whole list is the single node 0. The answer must follow the same rule. The list can be long (up to 1000 digits), far more digits than a 64-bit integer can hold.
Function
plusOne(head: ListNode) → ListNodeExamples
Example 1
head = [4,0,7]return = [4,0,8]The list stores 407, and 407 + 1 = 408. Only the last digit changes.
Example 2
head = [2,9,9]return = [3,0,0]The list stores 299, and 299 + 1 = 300. Both 9s at the end become 0 and pass a carry to the left, so the 2 becomes 3.
Example 3
head = [9,9,9,9]return = [1,0,0,0,0]The list stores 9999, and 9999 + 1 = 10000. Every digit is 9, so every node becomes 0 and a new node holding 1 goes in front: the answer has five nodes.
Constraints
- The number of nodes in the list is in the range
[1, 1000]. 0 <= Node.val <= 9- The first node is not
0, unless the list is the single node0.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Add Two Numbers IIBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Subtract Forward-Order Linked-List NumbersMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Add Numbers Stored in Four-Digit ChunksZipRecruiter · ONSITE INTERVIEWZipRecruiter interview questions
- Add Two Numbers Stored as Linked ListsCapital One · ONSITE INTERVIEWCapital One interview questions
- Add NumbersCisco · OACisco interview questions
- Binary Linked List to DecimalJP Morgan Chase · OAJP Morgan Chase interview questions
- Add Forward Linked-List Numbers Using RecursionPeopleStrong · PHONE SCREENPeopleStrong interview questions
- Plus OneDruva · ONSITE INTERVIEW
- Rotate a Flat Image ClockwiseGoogle · ONSITE INTERVIEWGoogle interview questions
- Detect a Loop in a Linked ListEPAM · ONSITE INTERVIEWEPAM interview questions
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)