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.
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
- We define a
ListNodeclass to represent each node in the linked list, with a
nextpointer to the next node.
segregate_even_oddfunction takes the head of the linked list as input and initializes two dummy nodes for even and odd lists.
- 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.
- 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.
- The even and odd lists are returned.
- We create a sample linked list and call the segregation function on it. We then print the original, even, and odd lists.