Problem statement

https://binarysearch.com/problems/Back-to-Front-Linked-List/

Solution

Variation of Leetcode 0143. Reorder List, but here we need to start from last element.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def solve(self, head):
        if not head or not head.next: return head
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        prev, curr = None, slow.next
        while curr:
            nextt = curr.next
            curr.next = prev
            prev = curr
            curr = nextt    
        slow.next = None
        
        head1, head2 = prev, head
        while head2:
            nextt = head1.next
            head1.next = head2
            head1 = head2
            head2 = nextt

        return prev