143. Reorder List

Problem Link

To solve this problem in-place, we first use the slow and fast pointer technique to find the middle of the linked list. When the loop ends, slow points to the middle node.

Next, we split the list into two halves by setting slow.next = None. We then reverse the second half of the list using a standard single-pass reversal, keeping track of the previous and next pointers.

Finally, we merge the two halves by alternating nodes from the first half and the reversed second half. During this process, we store the next pointers of both lists before re-linking, ensuring that no nodes are lost. The reordering continues until all nodes from the second half are merged back into the list.

---

Runtime Complexity

Time: \(O(n)\)

Space: \(O(1)\)

PythonGo

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        curr = slow.next
        prev = slow.next = None
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        first, second = head, prev
        while first and second:
            next1, next2 = first.next, second.next
            first.next = second
            second.next = next1
            first = next1
            second = next2

func reorderList(head *ListNode) {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    curr := slow.Next
    slow.Next = nil
    var prev, next *ListNode

    for curr != nil {
        next = curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }

    first, second := head, prev
    var next1, next2 *ListNode
    for first != nil && second != nil {
        next1, next2 = first.Next, second.Next
        first.Next = second
        second.Next = next1
        first, second = next1, next2
    }
}

---