143. Reorder List

url: https://leetcode.com/problems/reorder-list/description/

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

   1   ->  2   ->  3   ->  4   ->  5   ->  6    ->  null
=> 1   ->  6   ->  2   ->  5   ->  3   ->  4    ->  null

📝 Solution

Approach

To solve the problem 143. Reorder List, we need to identify a pattern that simplifies the solution.

In essence, we need to reorder the list by alternately placing the first and last elements until we reach the middle.
Strategy:

1. Find the middle and split the LL
   
   • To reorder the list, we first need to find the middle to divide it into two separate parts. The challenge here is finding the middle node efficiently in a singly linked list. A brute-force approach would involve iterating through all nodes to count them, then traversing again from the head to reach the middle, but this is inefficient.
     Using the fast & slow pointer algorithm, allows us to locate the middle in a single pass.
     

     This approach not only finds the middle efficiently but is also commonly used to detect cycles in a linked list. (a.k.a 🐰 & 🐢)
     

    # set pointers at the start line
    fast = slow = head
    # edge case: odd or even length?
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
   

   We need to check if the linked list length is odd or even. This is why we use fast and fast.next in the while condition.

2. Reverse the rear LL
   • By creating null node at the beggining, we can reverse the direction.

        null          4   ->  5   ->  6   ->  null
        null    <-    4       5   ->  6   ->  null
        null    <-    4   <-  5       6   ->  null
        null    <-    4   <-  5   <-  6       null
     

     To implement this logic, we use three pointers:
     

   • prev: Points to the previous node, starting from null.
   • curr: Points to the current node that we want to redirect.
   • temp: pointing he next node of curr to proceed with the next redirecting

      prev = None
      curr = slow # `slow` is the middle from step 1
      while curr:
       temp = curr.next
       curr.next = prev
       prev = curr
       curr = temp
     

3. Merge LLs
   • At the beginning of this stage, we have two linked lists., so we need to merge them into a single LL.
     

    1   ->  2   ->  3   ->  null
    6   ->  5   ->  4   ->  null
   
    =>
   
    1   ->  6   ->  2   ->  5   ->  3   ->  4    ->  null
   

    first = head
    second = prev   #prev stopped at the last element from step 2
    while second.next:
        first.next, first = second, first.next
        second.next, second = first, second.next
   

💻 Code

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        # set pointers at the start line
        fast = slow = head
        # edge case: odd or even length?
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        prev = None
        curr = slow # slow is the middle from step 1
        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp

        first = head
        second = prev   #`prev` stopped at the last element from step 2
        while second.next:
            first.next, first = second, first.next
            second.next, second = first, second.next