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

This is a Python program to move all even numbers before all the odd numbers in a linked list.

The program creates a linked list and modifies the linked list so that all even numbers appear before all the odd numbers in the list.

1. Create a class Node with instance variables data and next.
2. Create a class LinkedList with instance variables head and last_node.
3. The variable head points to the first element in the linked list while last_node points to the last.
4. Define methods get_node, get_prev_node, insert_at_beg, remove, append and display.
5. The method get_node takes an index as argument and traverses the list from the first node that many times to return the node at that index.
6. The method get_prev_node takes a reference node as argument and returns the previous node.
7. The method display traverses the list from the first node and prints the data of each node.
8. The method append appends a node with the data item passed to the end of the list.
9. The method insert_at_beg prepends a node to the list.
10. The method remove removes the node passed to it from the list.
11. Define the function move_even_before_odd which takes a linked list as argument.
12. The function move_even_before_odd removes the even elements in the list and prepends them to the front.
13. Create an instance of LinkedList, append data to it and modify the list such that all even numbers appear before the odd numbers.

Here is the source code of a Python program to move all even numbers before all the odd numbers in a linked list. The program output is shown below.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
class LinkedList:
    def __init__(self):
        self.head = None
        self.last_node = None
 
    def append(self, data):
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next
 
    def display(self):
        current = self.head
        while current:
            print(current.data, end = ' ')
            current = current.next
 
    def get_node(self, index):
        current = self.head
        for i in range(index):
            if current is None:
                return None
            current = current.next
        return current
 
    def get_prev_node(self, ref_node):
        current = self.head
        while (current and current.next != ref_node):
            current = current.next
        return current
 
    def insert_at_beg(self, new_node):
        if self.head is None:
            self.head = new_node
        else:
            new_node.next = self.head
            self.head = new_node
 
    def remove(self, node):
        prev_node = self.get_prev_node(node)
        if prev_node is None:
            self.head = self.head.next
        else:
            prev_node.next = node.next
 
 
def move_even_before_odd(llist):
    current = llist.head
    while current:
        temp = current.next
        if current.data % 2 == 0:
            llist.remove(current)
            llist.insert_at_beg(current)
        current = temp
 
 
a_llist = LinkedList()
 
data_list = input('Please enter the elements in the linked list: ').split()
for data in data_list:
    a_llist.append(int(data))
 
move_even_before_odd(a_llist)
 
print('The new list: ')
a_llist.display()

1. An instance of LinkedList is created.
2. The user is prompted to enter the data items for the list.
3. The function move_even_before_odd is called to move all the even numbers before all the odd numbers in the list.
4. The linked list is displayed.

Case 1:
Please enter the elements in the linked list: 3 1 0 4 30 12
The new list: 
12 30 4 0 3 1 
 
Case 2:
Please enter the elements in the linked list: 1 2
The new list: 
2 1 
 
Case 3:
Please enter the elements in the linked list: 1 2 3 4 5
The new list: 
4 2 1 3 5

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.