Leetcode 2816: Double a Number Represented as a Linked List
You are given the head of a non-empty linked list representing a non-negative integer, where each node contains a single digit of the number. Your task is to double the integer represented by the linked list and return the resulting number as a new linked list.
Problem
Approach
Steps
Complexity
Input: The input consists of the head of a non-empty linked list where each node contains a single digit of a number.
Example: head = [1, 8, 9]
Constraints:
• 1 <= number of nodes <= 10^4
• 0 <= Node.val <= 9
• The input is generated such that the list represents a number that does not have leading zeros, except the number 0 itself.
Output: Return the head of the linked list representing the number after doubling it.
Example: head = [3, 7, 8]
Constraints:
• The returned list must correctly represent the doubled number.
Goal: The goal is to double the number represented by the linked list and return the result as a new linked list.
Steps:
• 1. Traverse the linked list to calculate the number it represents.
• 2. Double the number.
• 3. Convert the doubled number back into a linked list and return it.
Goal: The input linked list contains integers between 0 and 9, and its size is within the specified range.
Steps:
• 1 <= number of nodes <= 10^4
• 0 <= Node.val <= 9
Assumptions:
• The linked list represents a valid number without leading zeros.
• Input: head = [1, 8, 9]
• Explanation: The number represented by the linked list is 189. Doubling 189 gives 378, which is returned as the new linked list [3, 7, 8].
Approach: We can traverse the linked list to convert it into a number, double it, and then convert the result back into a new linked list.
Observations:
• The number can be represented as a sum of digits multiplied by powers of 10.
• It may be beneficial to use a recursive approach to handle the carry during the doubling process.
Steps:
• 1. Define a helper function to traverse the linked list and compute the carry while doubling the number.
• 2. Use the carry to add digits back into the linked list.
• 3. Return the head of the new linked list representing the doubled number.
Empty Inputs:
• The input will never be an empty list as per the constraints.
Large Inputs:
• For large lists, we must ensure efficient traversal and handling of the doubled number.
Special Values:
• The number 0 should return 0 when doubled.
Constraints:
• The algorithm must handle lists with up to 10^4 nodes efficiently.
int pin(ListNode* head) {
if(head == NULL) return 0;
int val = pin(head->next);
int num = head->val;
num = num * 2 + val;
head->val = num % 10;
return num/10;
}
ListNode* doubleIt(ListNode* head) {
int num = pin(head);
while(num > 0) {
int c = num % 10;
num /= 10;
ListNode* node = new ListNode(c);
node->next = head;
head = node;
}
return head;
}
1 : Function Definition
int pin(ListNode* head) {
Define the function `pin` which is responsible for traversing the linked list recursively and calculating the carry for doubling the number.
2 : Condition Check
if(head == NULL) return 0;
Base case of recursion: If the node is NULL, return 0 (no carry).
3 : Recursive Call
int val = pin(head->next);
Recursively call `pin` to process the next node in the linked list and obtain the carry from the next digit.
4 : Node Processing
int num = head->val;
Extract the value of the current node.
5 : Computation
num = num * 2 + val;
Double the current node's value and add the carry from the recursive call.
6 : Update Node
head->val = num % 10;
Update the current node's value to the unit digit of the doubled number.
7 : Return Carry
return num / 10;
Return the carry (higher digit) to the previous recursion level.
8 : Function Definition
ListNode* doubleIt(ListNode* head) {
Define the function `doubleIt` which handles doubling the number represented by the linked list.
9 : Call pin
int num = pin(head);
Call `pin` to get the carry and process the digits of the linked list.
10 : While Loop
while(num > 0) {
Loop to handle the remaining carry and create new nodes for the doubled number.
11 : Extract Digit
int c = num % 10;
Extract the unit digit of the carry.
12 : Update Carry
num /= 10;
Update the carry by removing the processed unit digit.
13 : Create Node
ListNode* node = new ListNode(c);
Create a new node with the extracted digit.
14 : Insert Node
node->next = head;
Insert the new node at the beginning of the list (to maintain the correct order of digits).
15 : Update Head
head = node;
Update the head of the linked list to point to the newly created node.
16 : Return Head
return head;
Return the head of the updated linked list representing the doubled number.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The solution involves traversing the entire linked list once, making the time complexity O(n), where n is the number of nodes.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) because we need to store the linked list of size n.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus