Learn Programming and technology with ease @ developerpublish.com

HomePythonPython Program to Segregate Even and Odd Nodes in a Linked List

# 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.

## Input/Output

### You May Also Like

#### Python Program to Remove Duplicates from a Linked List

In this Python program, we will create a singly linked list and remove duplicate elements from it. A linked list...

#### Python Program to Solve the Celebrity Problem

This Python program solves the Celebrity Problem by finding a person who is known by everyone but does not know...

#### Python Program to Solve n-Queen Problem with Recursion

This Python program uses a recursive approach to solve the n-Queens problem. It explores all possible combinations of queen placements...