Reorder Linked List in DSA Python - Time & Space Complexity

Time Complexity: Reorder Linked List

O(n)

Understanding Time Complexity

We want to understand how the time needed to reorder a linked list changes as the list gets bigger.

Specifically, how the steps grow when we rearrange nodes from start and end alternately.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head):
    if not head or not head.next:
        return
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    prev, curr = None, slow.next
    slow.next = None
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

This code reorders a linked list by first finding the middle, reversing the second half, then merging both halves alternately.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing the linked list multiple times using loops.
• How many times: Three main loops: one to find the middle, one to reverse the second half, and one to merge the two halves.

How Execution Grows With Input

Each loop goes through about half or all of the list nodes, so the total steps grow roughly in a straight line with the number of nodes.

Input Size (n)	Approx. Operations
10	About 30 steps (3 passes of ~10 nodes)
100	About 300 steps
1000	About 3000 steps

Pattern observation: The operations increase linearly as the list size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to reorder grows directly in proportion to the number of nodes in the list.

Common Mistake

[X] Wrong: "Reversing the second half or merging halves takes extra nested loops, so complexity is O(n²)."

[OK] Correct: Each loop runs separately over parts of the list without nesting inside each other, so total steps add up linearly, not multiply.

Interview Connect

Understanding this helps you explain how to efficiently reorder linked lists, a common task in coding challenges and real-world data handling.

Self-Check

"What if we used recursion to reverse the second half instead of a loop? How would the time complexity change?"