Odd Even Linked List

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. The first node is considered odd, and the second node is even, and so on. Note that the relative order inside both the even and odd groups should remain as it was in the input. You must solve the problem in O(1) extra space complexity and O(n) time complexity.

For example, if the input linked list is [1,2,3,4,5], the output should be [1,3,5,2,4]. Another example is [2,1,3,5,6,4,7], and the output should be [2,3,6,7,1,5,4]. How do you approach this problem?

# Odd Even Linked List

## Problem Description

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*. The first node is considered odd, and the second node is even, and so on. Note that the relative order inside both the even and odd groups should remain as it was in the input. You must solve the problem in `O(1)` extra space complexity and `O(n)` time complexity.

**Example 1:**

Input: `head = [1,2,3,4,5]`
Output: `[1,3,5,2,4]`

**Example 2:**

Input: `head = [2,1,3,5,6,4,7]`
Output: `[2,3,6,7,1,5,4]`

## Naive Solution

A naive solution would involve traversing the linked list and storing the values of odd and even indexed nodes into separate arrays. Then, create a new linked list by first appending the odd indexed values and then the even indexed values. This approach requires O(n) extra space for the arrays.

## Optimal Solution

The optimal solution involves rearranging the nodes in-place using two pointers. We maintain two pointers, one for the odd nodes and one for the even nodes. We iterate through the linked list, moving the odd nodes to the odd list and the even nodes to the even list.  Finally, we connect the end of the odd list to the head of the even list.

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

def odd_even_list(head):
    if not head:
        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

    odd.next = even_head
    return head

# Example Usage:
# Create a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> None
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))

# Call the function
new_head = odd_even_list(head)

# Print the result
current = new_head
while current:
    print(current.val, end=" -> ")
    current = current.next
print("None") # Output: 1 -> 3 -> 5 -> 2 -> 4 -> None

Big(O) Run-time Analysis

The time complexity of the optimal solution is O(n), where n is the number of nodes in the linked list. This is because we iterate through the linked list once to rearrange the nodes.

Big(O) Space Usage Analysis

The space complexity of the optimal solution is O(1), as we are rearranging the nodes in-place and not using any extra space that scales with the input size.

Edge Cases

1. Empty List: If the input linked list is empty (head = None), the function should return None without any errors.
2. Single Node List: If the input linked list contains only one node, the function should return the head of the list as is, since there are no even nodes to move.
3. Two Node List: If the input linked list contains only two nodes, the function should return the head of the list with the nodes in the original order (odd followed by even).
4. Even Number of Nodes: If the input linked list contains an even number of nodes, the function should correctly group the odd and even nodes without any issues.
5. Odd Number of Nodes: If the input linked list contains an odd number of nodes, the function should correctly group the odd and even nodes without any issues.

These edge cases are handled correctly in the provided Python code.