# Python Program to Segregate Even and Odd Nodes in a Linked List

In this Python program, we’ll create a linked list and segregate its nodes into two separate lists – one for even-valued nodes and another for odd-valued nodes.

## Problem Statement

Given a linked list, the task is to segregate its nodes into two separate linked lists – one containing all the even-valued nodes and the other containing all the odd-valued nodes, while maintaining the relative order of the nodes within each list.

## Python Program to Segregate Even and Odd Nodes in a Linked List

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

while current:
if current.value % 2 == 0:  # even
even_tail.next = current
even_tail = even_tail.next
else:  # odd
odd_tail.next = current
odd_tail = odd_tail.next

current = current.next

odd_tail.next = None

# Helper function to print linked list
while current:
print(current.value, end=" -> ")
current = current.next
print("None")

# Creating the linked list: 1 -> 2 -> 3 -> 4 -> 5
for i in range(2, 6):
current.next = ListNode(i)
current = current.next

print("Even Nodes:")

print("Odd Nodes:")
```

## How It Works

1. We define a `ListNode` class to represent each node in the linked list, with a `value` and a `next` pointer to the next node.
2. The `segregate_even_odd` function takes the head of the linked list as input and initializes two dummy nodes for even and odd lists.
3. We iterate through each node of the original linked list:
• If the node’s value is even, we append it to the even list.
• If the node’s value is odd, we append it to the odd list.
4. Finally, we connect the tail of the even list to the head of the odd list, and set the tails’ next pointers to None to terminate the two lists.
5. The even and odd lists are returned.
6. We create a sample linked list and call the segregation function on it. We then print the original, even, and odd lists.