Problem statement

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

Solution

We can create list from linked list, then fold our list and then create linked list back.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, head):
        arr, cur = [], head
        while cur:
            arr.append(cur.val)
            cur = cur.next

        n = len(arr)
        for i in range(n // 2):
            arr[~i] += arr[i]

        i = n // 2
        ans = cur = LLNode(arr[i])
        while i + 1 < n:
            i += 1
            cur.next = cur = LLNode(arr[i])
        return ans

Remark

It is also possible to do it in O(1) additional space: we need to find middle, reverse the second half and then add it to the first half.