## Description

https://leetcode.com/problems/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.

**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]

**Constraints:**

- The number of nodes in the linked list is in the range
`[0, 10`

.^{4}] `-10`

^{6}<= Node.val <= 10^{6}

**Follow up:** Could you solve it in `O(1)`

space complexity and `O(nodes)`

time complexity?

## Explanation

Create an odd list and an even list, then combine together.

## Python Solution

```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
odd_dummy = ListNode(0)
even_dummy = ListNode(0)
odd_node = odd_dummy
even_node = even_dummy
index = 0
while head != None:
if index % 2 == 0:
odd_node.next = ListNode(head.val)
odd_node = odd_node.next
else:
even_node.next = ListNode(head.val)
even_node = even_node.next
head = head.next
index += 1
odd_node.next = even_dummy.next
return odd_dummy.next
```

- Time complexity: O(N).
- Space complexity: O(1).

## One Thought to “LeetCode 328. Odd Even Linked List”