Mirrored Difference Update

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given the head of a singly linked list with n nodes. Your task is to modify the values of the nodes in-place according to a specific "mirrored difference" rule.

The update rule is as follows:

The value of the 1st node should be updated to (Value of Last Node) - (Original Value of 1st Node).

The value of the 2nd node should be updated to (Value of 2nd to Last Node) - (Original Value of 2nd Node).

The value of the 3rd node should be updated to (Value of 3rd to Last Node) - (Original Value of 3rd Node).

...and so on.

This pattern continues until the pointers from the start and the end of the list meet or cross. If the list has an odd number of nodes, the middle node's value remains unchanged.

After modifying the list, your function should return its head.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first and only line of input contains the node data for the linked list, separated by single spaces. The input is terminated by -1.

Output Format:

Print a single line containing the updated values of the linked list nodes, separated by spaces.

Note:

A naive approach would be O(N^2). To solve this efficiently in O(N) time, you need a way to access the "mirrored" node from the end of the list for each node at the beginning. This can be achieved using a "fast and slow pointer" to find the middle, reversing the second half of the list, performing the updates, and then re-reversing the second half to restore the list's structure.

Sample Input 1:

10 4 5 3 6 -1

Sample Output 1:

-4 -1 0 3 6

Explanation for Sample 1:

Original list: 10 -> 4 -> 5 -> 3 -> 6
ptr1 at 10, ptr2 at 6. ptr1.val = 6 - 10 = -4.
ptr1 at 4, ptr2 at 3. ptr1.val = 3 - 4 = -1.
ptr1 at 5, ptr2 at 5. ptr1.val = 5 - 5 = 0.
Final list: -4 -> -1 -> 0 -> 3 -> 6.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= Number of nodes <= 1000
-1000 <= Node Value <= 1000

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Mirrored Difference Update

Console