mediumLinked ListsPattern: Recursive Approach
Recursive Linked List Value Transformation Solution
Problem Statement
Given the `head` of a singly linked list and two integers, `X` and `Y`. Implement a function `transformList` that recursively modifies the `val` of each node in the list. For each node, if its `val` is strictly less than `Y`, increment `val` by `X`. Otherwise, decrement `val` by `X`. The function should return the `head` of the modified linked list.
Examples
Example 1:
Input:head = 1 -> 5 -> 8 -> 2 -> NULL, X = 3, Y = 6
Output:4 -> 8 -> 5 -> 5 -> NULL
Explanation: Nodes with value < 6 are incremented by 3, others are decremented by 3. (1+3=4), (5+3=8), (8-3=5), (2+3=5).
Example 2:
Input:head = 10 -> 20 -> 30 -> NULL, X = 5, Y = 0
Output:5 -> 15 -> 25 -> NULL
Explanation: Since all node values (10, 20, 30) are >= 0, each is decremented by 5. (10-5=5), (20-5=15), (30-5=25).
Constraints
- 0 <= Number of nodes <= 10^4
- -10^9 <= Node.val <= 10^9
- -10^9 <= X <= 10^9
- -10^9 <= Y <= 10^9
Time: O(N) Space: O(N)
The optimal approach leverages recursion as specified by the problem. It defines a base case where if the current node is `null`, the recursion stops. Otherwise, it processes the current node's `val` based on the given conditions, then recursively calls itself for `head.next`, ensuring each node is visited and modified exactly once. This results in O(N) time complexity and O(N) space complexity due to the recursion stack.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def transformList(head: ListNode, X: int, Y: int) -> ListNode:
"""
Transforms the values of nodes in a linked list recursively.
For each node, if its val is less than Y, it increments by X.
Otherwise, it decrements by X.
Args:
head: The head of the linked list.
X: The value to add or subtract.
Y: The threshold value.
Returns:
The head of the modified linked list.
"""
# Base case: if the list is empty, return None
if head is None:
return None
# Transform the current node's value
if head.val < Y:
head.val += X
else:
head.val -= X
# Recursively call the function for the rest of the list
head.next = transformList(head.next, X, Y)
# Return the current head (which might be the original head or a modified one)
return head
# Driver code to read input and run the solution
def main():
# Read X and Y
line1 = sys.stdin.readline().strip().split()
X = int(line1[0])
Y = int(line1[1])
# Read list values
line2 = sys.stdin.readline().strip()
list_values = []
if line2:
list_values = list(map(int, line2.split()))
# Construct the linked list
dummy_head = ListNode(0)
current = dummy_head
for val in list_values:
current.next = ListNode(val)
current = current.next
head = dummy_head.next
# Transform the list
modified_head = transformList(head, X, Y)
# Print the transformed list values
result = []
temp = modified_head
while temp is not None:
result.append(str(temp.val))
temp = temp.next
sys.stdout.write(' '.join(result) + '\n')
if __name__ == '__main__':
main()