Code-Memo

Reorder List

Given a singly linked list head, reorder it to alternate the nodes from the first half and the second half of the list.

Approach

1. Find the Middle:
   • Use two pointers (slow and fast) to find the middle of the linked list.
2. Reverse the Second Half:
   • Reverse the second half of the linked list starting from the node after slow.
3. Merge Two Halves:
   • Merge the first half and the reversed second half by alternating nodes.

Detailed Steps

• Initialization:
  • Check if head or head.next is None, indicating no or only one node, respectively.
• Find the Middle:
  • Use two pointers (slow moves one step at a time, fast moves two steps at a time) to find the middle of the linked list (slow will be at the middle node).
• Reverse the Second Half:
  • Reverse the linked list starting from slow.next. Set previous to None and iterate through the second half, reversing pointers.
• Merge Two Halves:
  • Use two pointers (first and second) to merge the original first half (head) and the reversed second half (previous).

Time Complexity

• The time complexity of this approach is ( O(n) ), where ( n ) is the number of nodes in the linked list. We traverse the list twice and reverse one half, which is efficient for this problem size.

# 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:
        if not head or not head.next:
            return
        
        # find the middle
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # reverse the second half
        previous = None
        current = slow
        while current:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        
        # merge head with previous
        first, second = head, previous
        while second.next:
            temp1, temp2 = first.next, second.next
            first.next = second
            second.next = temp1
            first, second = temp1, temp2