mediumLinked ListsPattern: Recursive Approach
Collect Linked List Node Values Recursively Solution
Problem Statement
You are given the `head` of a singly linked list. Each node in the linked list has an integer `val` and a pointer `next` to the next node. Your task is to implement a function that recursively traverses the linked list from the `head` and collects all node values into a new list (e.g., an array or ArrayList) in the order they appear. The function should return this collected list.
Examples
Example 1:
Input:Linked List: 1 -> 2 -> 3 -> 4 -> NULL
Output:undefined
Explanation: The function recursively visits each node, collecting its value into a list in traversal order.
Example 2:
Input:Linked List: 7 -> NULL
Output:undefined
Explanation: The list contains only one node, so its value is collected.
Constraints
- 0 <= Number of nodes in the list <= 1000
- -1000 <= Node.val <= 1000
- Node values are not necessarily unique.
Time: O(N) Space: O(N)
The optimal recursive approach involves using an accumulator pattern. An empty list is initialized and passed as an argument to the recursive helper function. Each recursive call adds the current node's value to this single, accumulating list and then calls itself with the next node. This avoids repeated list concatenations, leading to O(N) time and O(N) space complexity.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
import json
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def collect_node_values(head, accumulator=None):
if accumulator is None:
accumulator = []
if head is None:
return accumulator
accumulator.append(head.val)
return collect_node_values(head.next, accumulator)
def build_linked_list(arr):
if not arr:
return None
head = ListNode(arr[0])
current = head
for i in range(1, len(arr)):
current.next = ListNode(arr[i])
current = current.next
return head
def main():
line = sys.stdin.readline().strip()
nums = []
if line:
nums_str = line.split(' ')
nums = [int(x) for x in nums_str if x.strip()]
head = build_linked_list(nums)
result = collect_node_values(head)
print(json.dumps(result))
if __name__ == '__main__':
main()