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

def segregate_even_odd(head):
    even_head = even_tail = ListNode(None)
    odd_head = odd_tail = ListNode(None)

    current = head

    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

    even_tail.next = odd_head.next
    odd_tail.next = None

    return even_head.next, odd_head.next

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

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

print("Original Linked List:")
print_linked_list(head)

even_head, odd_head = segregate_even_odd(head)

print("Even Nodes:")
print_linked_list(even_head)

print("Odd Nodes:")
print_linked_list(odd_head)

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