MediumNo. 0143

Reorder List — LeetCode 143 Python Solution

Topics
Stack, Recursion, Linked List, Two Pointers
On study lists
Blind 75 and NeetCode 150
Reading time
5 min

The 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.

Example

Example
L0 → L1 → … → Ln - 1 → Ln

Python solution

PythonSolution
# 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:
        fast = slow = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        cur = slow.next
        slow.next = None

        pre = None
        while cur:
            t = cur.next
            cur.next = pre
            pre, cur = cur, t
        cur = head

        while pre:
            t = pre.next
            pre.next = cur.next
            cur.next = pre
            cur, pre = pre.next, t

Complexity

Time
O(n)where n is the length of the linked list
Space · auxiliary
O(1)

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 143. Reorder List is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 143. Reorder List?

LeetCode 143. Reorder List is rated Medium on LeetCode.

What is the time complexity of LeetCode 143. Reorder List?

The Python solution on this page runs in O(n), where n is the length of the linked list.

What is the space complexity of LeetCode 143. Reorder List?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 143. Reorder List cover?

LeetCode 143. Reorder List is tagged Stack, Recursion, Linked List and Two Pointers on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.