143. Reorder List

import pytest

from node import ListNode
from solution import Solution


@pytest.mark.parametrize('values, expected', [
    ([1,2,3,4], [1,4,2,3]),
    ([1,2,3,4,5], [1,5,2,4,3]),
])
class Test:
    def test_solution(self, values, expected):
        sol = Solution()
        head = self._build_list(values)
        sol.reorderList(head)
        result = self._format(head)
        assert result == expected

    def _build_list(self, values: list[int]) -> ListNode | None:
        root = ListNode()
        node = root
        for v in values:
            node.next = node = ListNode(v)

        return root.next

    def _format(self, head: ListNode | None) -> list[int]:
        values = []
        while head is not None:
            values.append(head.val)
            head = head.next

        return values

from typing import Optional

from node import ListNode

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # Find the start node of the right part (to be inverted).
        p1 = p2 = head
        while p2 is not None:
            p2 = p2.next
            if p2 is None:
                break
            p1 = p1.next
            p2 = p2.next

        right, p1.next = p1.next, None

        # Invert the right half list.
        prev = None
        curr = right
        while curr is not None:
            curr.next, prev, curr = prev, curr, curr.next

        right = prev

        # Merge left half and inverted right half into one.
        while right is not None:
            head.next, right.next, head, right = right, head.next, head.next, right.next