0037 - Reorder Linked List

You are given the head of a singly linked-list.

The positions of a linked list of length = 7 for example, can intially be represented as:

[0, 1, 2, 3, 4, 5, 6]

Reorder the nodes of the linked list to be in the following order:

[0, 6, 1, 5, 2, 4, 3]

Notice that in the general case for a list of length = n the nodes are reordered to be in the following order:

[0, n-1, 1, n-2, 2, n-3, ...]

You may not modify the values in the list's nodes, but instead you must reorder the nodes themselves.

Example 1:

Input: head = [2,4,6,8]

Output: [2,8,4,6] Example 2:

Input: head = [2,4,6,8,10]

Output: [2,10,4,8,6]

• Find the middle of the list using slow/fast pointers
• Reverse the second half of the list
• Merge the two halves alternately
• Time Complexity: O(n) - one pass for each step
• Space Complexity: O(1) - only using pointers
• https://www.youtube.com/watch?v=S5bfdUTrKLM

In [2]:

# 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:
        #find middle
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # reverse second half
        current=slow.next
        prev,slow.next = None,None      #Divivde list into 2 parts
        while current:
            next_step = current.next
            current.next=prev
            prev = current
            current = next_step

        #after this loop current will be set to None

        # merge 2 halfs
        first,second = head,prev
        while second:
            first_next, second_next = first.next, second.next
            first.next=second
            second.next=first_next

            first = first_next
            second = second_next

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[2], line 7
      4         self.val = val
      5         self.next = next
----> 7 class Solution:
      8     def reorderList(self, head: Optional[ListNode]) -> None:
      9         #find middle
     10         slow, fast = head, head.next

Cell In[2], line 8, in Solution()
      7 class Solution:
----> 8     def reorderList(self, head: Optional[ListNode]) -> None:
      9         #find middle
     10         slow, fast = head, head.next
     11         while fast and fast.next:

NameError: name 'Optional' is not defined