algoadvance

Clarifying Questions

1. Input Format: Are we given the head of a singly linked list, and we need to reorder it in-place without changing the node values (only changing pointers)?
2. Output Format: Do we need to return the head of the modified list, or just modify the list in place without returning anything?
3. Constraints: Are there any constraints on the number of nodes in the list? What should we do if the list has less than three nodes?

Assuming:

• The input is the head of a singly linked list.
• We don’t need to return anything; the list should be modified in place.
• The list might have any number of nodes, including edge cases like 0, 1, or 2 nodes.

Strategy

The task is to reorder a list such that: Given L0 → L1 → … → Ln-1 → Ln, reorder it to L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

Steps:

1. Find the Middle of the List: Use the Fast and Slow pointer technique to find the middle node.
2. Reverse the Second Half: Reverse the list starting from the node next to the middle to the end.
3. Merge Two Halves: Merge the first half and the reversed second half alternating between nodes.

Detailed Steps:

1. Finding the Middle:
   • Use two pointers, slow and fast. Move slow by one step and fast by two steps until fast reaches the end.
   • Slow will point to the middle.
2. Reversing the Second Half:
   • From the next of the middle node to the end, reverse these nodes.
3. Merging:
   • Merge the nodes, where you take one node from the first half and one node from the reversed second half alternately.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head):
    if not head or not head.next:
        return
    
    # Step 1: Find the middle of the linked list
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: Reverse the second half of the list
    prev, curr = None, slow.next
    slow.next = None  # Cut the list into two halves
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    
    # Step 3: Merge the two halves
    first, second = head, prev
    while second:
        next_first, next_second = first.next, second.next
        first.next = second
        second.next = next_first
        first, second = next_first, next_second

# Example usage
# Let's create a list: 1->2->3->4
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)

reorderList(head)
# The list should be reordered to 1->4->2->3

Time Complexity

• Finding the middle: O(n)
• Reversing the second half: O(n/2) -> O(n)
• Merging two halves: O(n)

Overall, the time complexity is O(n) where n is the number of nodes in the list.

Space Complexity

• The algorithm runs in O(1) extra space, excluding the input and output list space.

Feel free to ask any further clarifying questions or simulating additional test cases to ensure the solution is robust!

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?