MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to Solve Odd Even Linked List

Written By

## Odd Even Linked List Introduction

The Odd Even Linked List problem asks us to group all the nodes with odd indices together followed by the nodes with even indices and return the reordered list. This problem can be solved with a simple approach by separating the odd and even nodes into two groups and then merging these two groups to obtain the final reordered list while maintaining the relative order of nodes within each group.

## Odd Even Linked List Problem

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.

### Example Inputs and Outputs

#### Example 1

Output: [1,3,5,2,4]

#### Example 2

Output: [2,3,6,7,1,5,4]

## Odd Even Linked List Solutions

To reorder the given linked list based on odd and even indices, we can follow a simple approach. We'll divide the linked list into two separate groups: one for nodes with odd indices and one for nodes with even indices. Then, we'll merge these two groups to obtain the final reordered list while maintaining the relative order of nodes within each group. We'll start by initializing two pointers: one for odd nodes and one for even nodes. Initially, the odd pointer will point to the head of the linked list, and the even pointer will point to the next node. We'll also keep track of the head of the even list to connect it later. Next, we'll iterate through the linked list, advancing the odd pointer by two steps and the even pointer by two steps in each iteration. This will separate the nodes into odd and even group while keeping their original order.

Finally, we'll merge the even list after the odd list by linking the last node of the odd group to the head of the even group. This will connect the two groups and give us the desired reordered list.

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

while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next

# Test case 1
# Expected output: 1 -> 3 -> 5 -> 2 -> 4
current = result1
while current:
print(current.val, end=" -> ")
current = current.next
print("None")``````

#### Time/Space Complexity Analysis

• Time Complexity: O(N), where n is the number of nodes in the linked list.
• Space Complexity: O(1), as we use a constant amount of extra space.