Technical Interview Question

You are given a singly linked list where the elements are sorted in ascending order. Write a function to modify the linked list so that all the nodes with odd indices come before the nodes with even indices. For example, given the linked list 1 -> 2 -> 3 -> 4 -> 5, the modified linked list should be 1 -> 3 -> 5 -> 2 -> 4.

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

def odd_even_linked_list(head: ListNode) -> ListNode:
    # Implement function here

Answer

def odd_even_linked_list(head: ListNode) -> ListNode:
    if head is None or head.next is None or head.next.next is None:
        return head

    odd_head = ListNode(-1)
    even_head = ListNode(-1)

    odd_curr = odd_head
    even_curr = even_head

    is_odd = True

    while head:
        if is_odd:
            odd_curr.next = head
            odd_curr = odd_curr.next
        else:
            even_curr.next = head
            even_curr = even_curr.next

        is_odd = not is_odd
        head = head.next

    even_curr.next = None
    odd_curr.next = even_head.next

    return odd_head.next

Explanation

1. We initialize two new linked lists, odd_head and even_head, with dummy values.
2. We iterate through the original linked list, appending odd-indexed and even-indexed nodes to their respective new linked lists (odd_head and even_head) based on a boolean is_odd flag.
3. After the iteration, we set the next pointer of even_curr to None to terminate the even list and merge it with the odd list by setting odd_curr.next to even_head.next.
4. Finally, we return the modified odd linked list (excluding the dummy node).