Add Two Numbers as Linked Lists

You are given two singly linked lists, where each list represents a positive number without any leading zeros.

Your task is to add these two numbers and return the sum as a linked list.

Example:

Input:

The first linked list is 1 -> 2 -> 3 -> 4 -> 5 -> NULL
The second linked list is 4 -> 5 -> NULL

Output:

The linked list representation of the summation is 1 -> 2 -> 3 -> 9 -> 0 -> NULL

Explanation:

The numbers represented are 12345 and 45. The sum is 12390, represented as a linked list 1 -> 2 -> 3 -> 9 -> 0 -> NULL.

Input:

The first line contains an integer 'T', the number of test cases.
Each test case consists of two lines of integers representing the linked list elements, terminated by -1. (-1 is not part of the list elements.)

Output:

For each test case, return the head of the linked list summation. Terminate the linked list elements with -1.

Constraints:

• 1 <= T <= 100
• 1 <= L <= 5000 (where L is the number of nodes in either of the linked lists)
• 0 <= data <= 9 (data is the value of a node, and -1 is not included in list elements)

Note:

You don't need to handle print operations. Just implement the given function.

Follow-Up:

Optimize the solution to achieve linear time and constant space complexity.