Linked List Folding

You are given a singly linked list node containing integer values. Take the first half of the linked list and fold over the second half and merge the intersecting nodes by taking their sum.

Constraints

• 1 ≤ n ≤ 100,000 where n is the number of nodes in node

https://binarysearch.com/problems/Linked-List-Folding

Examples

Example 1

Input

• node =

Output

• answer =

Explanation

We fold at the 1, which doesn’t change, and 2 and 3 get merged into 5.

Example 2

Input

• node =

Output

• answer =

Explanation

We fold the linked list so the 3 and 4 get merged into 7, and the 1 and 2 get merged into 3.

Solution