Reorder List

---

Intuition

• This problem is a combination of Reverse Linked List and Floyds Tortoise and Hare.
• Use Floyds Tortoise and Hare to find the middle of the list. Notice that the left half will always be $>=$ the right half.
• Reverse the second half of the linked list, first severing the two halves to prevent conflicts.
• Set first to last, and last to second first, moving all pointers until tail is None.

Complexity

Runtime

• $O(N)$

Space

• $O(1)$

Code

# 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.
        """
        slow = head
        fast = head
 
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        
        prev = None
        cur = slow.next
        slow.next = None
 
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        
        tail = prev
        orig_head = head
        while tail:
            head_nxt = head.next
            tail_nxt = tail.next
            head.next = tail
            tail.next = head_nxt
            head = head_nxt
            tail = tail_nxt
        
        return orig_head

Notes

Drive

Cards

START Basic Front: Reorder List Back: Reverse second half and sever END

---

References

• Reorder List