Reorder List

Leetcode #143

getting the correct idea is intuitive, but knowing how to implement it is quite tricky, had to watch the neetcode video to learn the method of using the slow and fast pointers, for example. also got tripped up and forgot to break the link between the first and second half initially.

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.

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

Example 2:
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 * 104].
1 ⇐ Node.val ⇐ 1000

Optimal Solution: (Reverse + Merge)

# 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: ListNode | None) -> None:
        """
        Do not return anything, modify head in-place instead.
        - find the middle (new end)
        - break into first half, second half
        - reverse second half
        - merge
        """
        # slow moves by 1 node, fast by 2
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        second = slow.next
 
        # reverse second 
        ## MUST BREAK LINK! 
        prev = slow.next = None
        while second:
            temp = second.next
            second.next = prev
            prev = second 
            second = temp
        
        first,second = head,prev
        while second:
            temp1 = first.next
            temp2 = second.next
            first.next = second
            second.next = temp1
            first, second = temp1, temp2