Linked List and String Reversal Patterns

MediumPython

Problem

Red Hat test tooling may need to transform textual data and linked-list representations during validation. Implement one function that performs three independent operations: reverse a string through a specified index, reverse a singly linked list, and merge two sorted singly linked lists.

Formal Specification

Implement solve(s, k, reverse_head, list1, list2):

Reverse the characters in s from index 0 through index k, inclusive. Leave the remaining suffix unchanged.
Reverse reverse_head in place and return the new head.
Merge list1 and list2, which are sorted in nondecreasing order, into one sorted linked list. Reuse the existing nodes rather than creating replacement value nodes.

Each linked list is represented as a nested JSON-compatible object with integer field value and nullable field next. The function returns a dictionary containing reversed_string, reversed_list, and merged_list, each in the same serialized linked-list format.

Constraints

1 <= len(s) <= 10^5
0 <= k < len(s)
Each linked list contains at most 10^5 nodes
Node values are integers in [-10^9, 10^9]
list1 and list2 are sorted in nondecreasing order
All linked lists are acyclic

Function Signature

def solve(s, k, reverse_head, list1, list2):

Formal Specification

Implement solve(s, k, reverse_head, list1, list2):

Reverse the characters in s from index 0 through index k, inclusive. Leave the remaining suffix unchanged.
Reverse reverse_head in place and return the new head.
Merge list1 and list2, which are sorted in nondecreasing order, into one sorted linked list. Reuse the existing nodes rather than creating replacement value nodes.