369. Plus One Linked List
Plus One Linked List (LeetCode 369) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Linked List Manipulation Patterns pattern, in the Addition of Numbers subpattern.
How to solve Plus One Linked List
Plus One Linked List is a Add Numbers Using Linked Lists problem, part of Linked List Manipulation Patterns. Master adding numbers represented as linked lists. Handle carry operations and different list lengths.
Work towards the solution in these steps:
- Consider how addition with carry is performed on numbers represented digit by digit; think about how this applies to linked lists.
- Since the digits are stored in forward order, think about how to process the list so you can add one starting from the least significant digit.
- One approach is to reverse the linked list to make addition easier, perform the addition, handle carry, and then reverse it back.
The reference solution runs in O(n) time and O(1) space.
The Plus One Linked List solution and editorial walks through the full approach with reference code.
Problem statement
You are given the head of a non-empty singly linked list head, where each node contains a single digit (0-9). The digits are stored in forward order, meaning the most significant digit comes first. The linked list represents a non-negative integer.
Your task is to add one to this integer and return the head of the resulting linked list. The solution must handle any necessary carry-over, including cases where the number of digits increases.
Return the head of the updated linked list.
Examples
Example 1
Input: {"head": [1, 2, 3]}
Output: [1, 2, 4]
Explanation: plus one to a simple number 123, resulting in 124.
Example 2
Input: {"head": [9, 9, 9]}
Output: [1, 0, 0, 0]
Explanation: plus one to 999 causes a carry over at every digit, resulting in 1000.
Topics and companies
Topics: Linked List, Math.
Reported in interviews at Google, Amazon.
How to practise Plus One Linked List on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Plus One Linked List in the code editor, or read the Plus One Linked List editorial for a worked solution with its approach and complexity analysis.
Where Plus One Linked List sits in the DSA pattern sheet
- Linked List Manipulation Patterns pattern guide
- Addition of Numbers subpattern
- The full DSA patterns sheet
Problems related to Plus One Linked List
Other problems that use the same Addition of Numbers and Linked List Manipulation Patterns techniques:
- Add Two Numbers — Medium, same subpattern
- Insert Greatest Common Divisors in Linked List — Medium, same pattern
- Intersection of Two Linked Lists — Easy, same pattern
- Merge Two Sorted Lists — Easy, same pattern
- Minimum Index Sum of Two Lists — Easy, same pattern
- Odd Even Linked List — Medium, same pattern
Plus One Linked List FAQ
What is the LeetCode number of Plus One Linked List?
Plus One Linked List is LeetCode problem 369, rated Medium.
What pattern is used to solve Plus One Linked List?
Plus One Linked List is a Add Numbers Using Linked Lists problem. It belongs to the Linked List Manipulation Patterns pattern, in the Addition of Numbers subpattern.
What is the time complexity of Plus One Linked List?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Plus One Linked List?
Plus One Linked List has been reported in interviews at Google, Amazon.