# Odd Even Linked List

**1. Clarify the problem:**
Before diving into solving the problem, let's clarify the requirements:

- We are given the head of a singly linked list.
- We need to rearrange the linked list such that all nodes with odd values appear before the nodes with even values while preserving the relative order of odd and even nodes.
- The modified linked list should maintain the original order of odd and even nodes.

**2. Analyze the problem:**
To solve this problem, we can use a two-pointer approach. We'll maintain two pointers, `odd`

and `even`

, to keep track of the current odd and even nodes, respectively. We'll also need two additional pointers, `even_head`

and `odd_tail`

, to remember the heads of the even sublist and the tail of the odd sublist.

**3. Design an algorithm:**
Here is the algorithm to solve the problem:

- If the input linked list is empty or has only one node, return the head as it is.
- Initialize four pointers:
`odd_head`

and`odd_tail`

to None.`even_head`

and`even`

to None.

- Iterate through each node in the linked list using a loop:
- If the node's value is odd (i.e., not divisible by 2):
- If
`odd_head`

is None, set both`odd_head`

and`odd_tail`

to the current node. - Otherwise, update the
`next`

pointer of`odd_tail`

to the current node, and move`odd_tail`

to the current node.

- If
- If the node's value is even (i.e., divisible by 2):
- If
`even_head`

is None, set both`even_head`

and`even`

to the current node. - Otherwise, update the
`next`

pointer of`even`

to the current node, and move`even`

to the current node.

- If

- If the node's value is odd (i.e., not divisible by 2):
- After the loop, if
`odd_head`

is None (i.e., there were no odd nodes), return`even_head`

as the modified linked list. - Otherwise, set the
`next`

pointer of`odd_tail`

to`even_head`

to connect the odd and even sublists. - If
`even`

is not None, set its`next`

pointer to None to terminate the even sublist. - Return
`odd_head`

as the modified linked list.

**4. Explain your approach:**
The approach involves iterating through the linked list and maintaining two pointers, `odd_tail`

and `even`

, to track the tail of the odd sublist and the current even node, respectively. We also keep track of the head of the even sublist using `even_head`

. We update the pointers as we encounter odd and even nodes, and finally connect the odd and even sublists together.

**5. Write clean and readable code:**

python

```
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head):
if not head or not head.next:
return head
odd_head = odd_tail = None
even_head = even = None
node = head
while node:
if node.val % 2 != 0:
if odd_head is None:
odd_head = odd_tail = node
else:
odd_tail.next = node
odd_tail = odd_tail.next
else:
if even_head is None:
even_head = even = node
else:
even.next = node
even = even.next
node = node.next
if odd_head is None:
return even_head
odd_tail.next = even_head
if even:
even.next = None
return odd_head
```

**6. Test your code:**
Let's test the code with different test cases to ensure its correctness:

Test case with an empty list:

- Input:
`head = None`

- Expected output:
`None`

- Input:
Test case with only one node:

- Input:
`head = ListNode(1)`

- Expected output:
`ListNode(1)`

- Input:
Test case with a list containing odd and even nodes:

- Input:scss

- Input:

`head = ListNode(1) head.next = ListNode(2) head.next.next = ListNode(3) head.next.next.next = ListNode(4) head.next.next.next.next = ListNode(5)`

- Expected output:
`ListNode(1) -> ListNode(3) -> ListNode(5) -> ListNode(2) -> ListNode(4)`

Test case with a list containing only even nodes:

- Input:scss

`head = ListNode(2) head.next = ListNode(4) head.next.next = ListNode(6)`

- Expected output:
`ListNode(2) -> ListNode(4) -> ListNode(6)`

Test case with a list containing only odd nodes:

- Input:scss

`head = ListNode(1) head.next = ListNode(3) head.next.next = ListNode(5)`

- Expected output:
`ListNode(1) -> ListNode(3) -> ListNode(5)`

python

```
# Test case 1: Empty list
head = None
print(oddEvenList(head)) # Output: None
# Test case 2: List with only one node
head = ListNode(1)
print(oddEvenList(head)) # Output: ListNode(1)
# Test case 3: List with odd and even nodes
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
print(oddEvenList(head)) # Output: ListNode(1) -> ListNode(3) -> ListNode(5) -> ListNode(2) -> ListNode(4)
# Test case 4: List with only even nodes
head = ListNode(2)
head.next = ListNode(4)
head.next.next = ListNode(6)
print(oddEvenList(head)) # Output: ListNode(2) -> ListNode(4) -> ListNode(6)
# Test case 5: List with only odd nodes
head = ListNode(1)
head.next = ListNode(3)
head.next.next = ListNode(5)
print(oddEvenList(head)) # Output: ListNode(1) -> ListNode(3) -> ListNode(5)
```

**7. Optimize if necessary:**
The current solution has a time complexity of O(n), where n is the length of the linked list. We iterate through each node once. The space complexity is O(1) as we only use a constant amount of additional space.

**8. Handle error cases:**
The code handles the cases where the input linked list is None or has only one node. It returns the head as it is in those cases.

**9. Discuss complexity analysis:**
The time complexity of the solution is O(n), where n is the length of the linked list. We iterate through each node once. The space complexity is O(1) as we only use a constant amount of additional space. The solution has a linear time complexity and constant space complexity.