# Solution For Odd Even Linked List

The Odd Even Linked List problem on LeetCode requires us to modify a given singly linked list such that all odd-indexed nodes come before the even-indexed nodes. Specifically, the modified list should have all the nodes at odd positions arranged first, followed by all the nodes at even positions. The nodes are numbered 1, 2, 3, …, n, where n is the length of the list.

Here’s a detailed solution to the problem:

1. Initialize two variables, one to keep track of the odd-node list (oddHead) and the other to keep track of the even-node list (evenHead) as null.
2. Traverse through the given linked list (head) and for each node check if it is at an odd or even position using the node number.
3. If the node is at an odd position, add it to the end of the odd-node list by checking if oddHead is null. If it is null, set oddHead to the current node. Otherwise, link the current node to the end of the odd-node list.
4. If the node is at an even position, add it to the end of the even-node list using the same approach as above.
5. After all the nodes have been traversed, link the end of the odd-node list to the start of the even-node list by checking if oddHead is null. If it is null, return evenHead. Otherwise, link the last node of the odd-node list to the first node of the even-node list and return oddHead.

Here’s the implementation of the solution in Python:

“`python
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:

``````    oddHead = oddTail = None
evenHead = evenTail = None
count = 1

if count % 2 == 1:
else:
oddTail = oddTail.next
else:
else:
evenTail = evenTail.next

count += 1

evenTail.next = None

``````

“`

In the above code, we first check if the given linked list has less than two nodes and if it does, we return it as is. We then initialize variables oddHead and evenHead to null. We also keep track of the tail nodes of both the odd and even lists, initialized to None. A variable count is also initialized to keep track of the node number, starting from 1. We traverse the given linked list using a while loop, keeping track of the node position using count.

If the current node is at an odd position, we add it to the odd list by checking if oddHead is null. If it is null, we set it to the current node and update the oddTail. Otherwise, we link the current node to the end of the odd list and update the oddTail. If the current node is at an even position, we add it to the even list in the same way.

After traversing all the nodes, we link the end of the odd list to the start of the even list by setting oddTail.next to evenHead. We also set evenTail.next to null to terminate the even list. Finally, we return oddHead as the modified linked list.

## Step by Step Implementation For Odd Even Linked List

```/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode oddEvenList(ListNode head) {
ListNode odd = head, even = head.next, evenHead = even;
while(even != null && even.next != null){
odd.next = odd.next.next;
even.next = even.next.next;
odd = odd.next;
even = even.next;
}
}
}```
```# 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:
if head is None:
return None
while even is not None and even.next is not None:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
```var oddEvenList = function(head) {
if(head === null) return null;
let odd = head;
let even = head.next;
let evenHead = even;

while(even !== null && even.next !== null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
};```
```/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
ListNode* odd = head;
ListNode* even = head->next;
ListNode* evenHead = even;
while(even != nullptr && even->next != nullptr) {
odd->next = odd->next->next;
odd = odd->next;
even->next = even->next->next;
even = even->next;
}
}
};```
```/**
* Definition for singly-linked list.
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int val=0, ListNode next=null) {
*         this.val = val;
*         this.next = next;
*     }
* }
*/
public class Solution {
public ListNode OddEvenList(ListNode head) {
//edge case - if head is null or there is only 1 node in the list
if(head == null || head.next == null){
}

//set up 2 pointers - one for the head of the odd list and one for the head of the even list
ListNode odd = head;
ListNode even = head.next;

//set up a pointer for the head of the even list so we can connect the odd list to the end of the even list later
ListNode evenHead = even;

//while there are still nodes in the list
while(even != null && even.next != null){
//set odd.next to the next odd node
odd.next = even.next;
//increment odd to the next odd node
odd = odd.next;
//set even.next to the next even node
even.next = odd.next;
//increment even to the next even node
even = even.next;
}

//set odd.next to the head of the even list so the odd list is now connected to the end of the even list