111 Odd Even Linked List - Group odd and even indexed nodes

 The Odd Even Linked List is a common linked list problem typically found in FAANG-level interviews. It involves reordering a singly linked list such that all nodes at odd indices come before all nodes at even indices, preserving the relative order among odd and even nodes.

Problem Statement

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

Note:

• The node position/index is considered starting from 1 (not 0).

• You must do this in O(1) space and O(n) time complexity.

Intuition

Separate the list into two:

• One list for nodes at odd indices

• One list for nodes at even indices

At the end, link the last node of the odd list to the head of the even list.

Algorithm

1. Edge case: If the list is empty or has one element, return the head.

2. Initialize:

   • odd pointing to the first node,

   • even pointing to the second node,

   • even_head pointing to the head of the even list (used for reconnecting).

3. Iterate while both odd.next and even.next are not null:

   • Link odd.next to odd.next.next

   • Move odd one step

   • Link even.next to even.next.next

   • Move even one step

4. Finally, link the last odd node to even_head.

Time and Space Complexity

• Time: O(n) — Each node is visited once.

• Space: O(1) — Only pointers are used.

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

def create_linked_list(arr):
    head = LinkedListNode(arr[0])

    current = head

    for k in arr[1:]:
        current.next= LinkedListNode(k)
        current = current.next

    return head

def print_linked_list(head):
    res = []
    current = head

    while current:
        res.append(str(current.val))
        current = current.next
    print("=>".join(res))

def odd_even_linkked_list(head):

    if not head or not head.next:
        return head
    
    odd = head
    even = head.next
    even_head = even

    while even and even.next:

        odd.next = even.next
        odd = odd.next

        even.next = odd.next
        even = even.next

    # now we have odd last ref and even_head first ref of even list , lets join together

    odd.next = even_head

    return head

k = create_linked_list([101,102,110,22,44,66,34,98])
print_linked_list(k)

print_linked_list(odd_even_linkked_list(k))