Reorder List Python Solution with Tests

Tested Python solution for LeetCode 143 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 143, Medium. Topics: Linked List, Two Pointers, Stack, Recursion. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 15 parametrized pytest cases, and a playground notebook:

lcpy gen -n 143   # by problem number
lcpy gen -s reorder_list   # by problem name

​

Problem

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

​

Examples

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

​

Constraints

• The number of nodes in the list is in the range [1, 5 * 10^4].
• 1 <= Node.val <= 1000

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from leetcode_py import ListNode


class Solution:
    # Time: O(n) where n is the number of nodes
    # Space: O(1) - only using constant extra space
    def reorder_list(self, head: ListNode[int] | None) -> None:
        """
        Reorder a linked list in-place: L0→L1→...→Ln-1→Ln becomes L0→Ln→L1→Ln-1→L2→Ln-2→...

        Algorithm:
        1. Find the middle of the list using slow/fast pointers
        2. Reverse the second half of the list
        3. Merge the first half and reversed second half alternately

        This approach uses O(1) space and O(n) time.
        """
        if not head or not head.next:
            return

        # Step 1: Find the middle of the list
        slow = fast = head
        while fast.next and fast.next.next:
            assert slow.next
            slow = slow.next
            fast = fast.next.next

        # Split the list into two halves
        second_half = slow.next
        slow.next = None  # Break the connection

        # Step 2: Reverse the second half
        prev = None
        current = second_half
        while current:
            next_temp = current.next
            current.next = prev
            prev = current
            current = next_temp
        second_half = prev

        # Step 3: Merge the two halves alternately
        first_half = head
        while second_half:
            assert first_half is not None
            # Store next nodes
            first_next = first_half.next
            second_next = second_half.next

            # Reorder: first -> second -> first_next
            first_half.next = second_half
            second_half.next = first_next

            # Move to next nodes
            first_half = first_next
            second_half = second_next

​

Complexity

Time	Space
O(n) where n is the number of nodes	O(1) - only using constant extra space

​

Tags

Grind, Blind 75, NeetCode 150, NeetCode 250, NeetCode All.