Separe los Nodes pares e impares en una lista enlazada – Part 1

Dada una lista enlazada de enteros, escriba una función para modificar la lista enlazada de modo que todos los números pares aparezcan antes que todos los números impares en la lista enlazada modificada. Además, mantén el mismo orden de los números pares e impares.
Ejemplos: 
 

Input: 17->15->8->12->10->5->4->1->7->6->NULL
Output: 8->12->10->4->6->17->15->5->1->7->NULL

Input: 8->12->10->5->4->1->6->NULL
Output: 8->12->10->4->6->5->1->NULL

// If all numbers are even then do not change the list
Input: 8->12->10->NULL
Output: 8->12->10->NULL

// If all numbers are odd then do not change the list
Input: 1->3->5->7->NULL
Output: 1->3->5->7->NULL

Método 1 
La idea es obtener un puntero al último Node de la lista. Y luego recorra la lista comenzando desde el Node principal y mueva los Nodes con valores impares desde su posición actual hasta el final de la lista.
Gracias a Blunderboy por sugerir este método.
Algoritmo: 
…1) Obtener puntero al último Node. 
…2) Mueva todos los Nodes impares hasta el final. 
……..a) Considere todos los Nodes impares antes del primer Node par y muévalos al final. 
……..b) Cambie el puntero de la cabeza para que apunte al primer Node par. 
……..b) Considere todos los Nodes impares después del primer Node par y muévalos al final. 
 

C++

// C++ program to segregate even and
//  odd nodes in a Linked List 
#include <bits/stdc++.h>
using namespace std;
  
/* a node of the singly linked list */
class Node 
{ 
    public:
    int data; 
    Node *next; 
}; 
  
void segregateEvenOdd(Node **head_ref) 
{ 
    Node *end = *head_ref; 
    Node *prev = NULL; 
    Node *curr = *head_ref; 
  
    /* Get pointer to the last node */
    while (end->next != NULL) 
        end = end->next; 
  
    Node *new_end = end; 
  
    /* Consider all odd nodes before the first 
     even node and move then after end */
    while (curr->data % 2 != 0 && curr != end) 
    { 
        new_end->next = curr; 
        curr = curr->next; 
        new_end->next->next = NULL; 
        new_end = new_end->next; 
    } 
  
    // 10->8->17->17->15 
    /* Do following steps only if 
    there is any even node */
    if (curr->data%2 == 0) 
    { 
        /* Change the head pointer to 
        point to first even node */
        *head_ref = curr; 
  
        /* now current points to
        the first even node */
        while (curr != end) 
        { 
            if ( (curr->data) % 2 == 0 ) 
            { 
                prev = curr; 
                curr = curr->next; 
            } 
            else
            { 
                /* break the link between
                prev and current */
                prev->next = curr->next; 
  
                /* Make next of curr as NULL */
                curr->next = NULL; 
  
                /* Move curr to end */
                new_end->next = curr; 
  
                /* make curr as new end of list */
                new_end = curr; 
  
                /* Update current pointer to
                next of the moved node */
                curr = prev->next; 
            } 
        } 
    } 
  
    /* We must have prev set before executing 
    lines following this statement */
    else prev = curr; 
  
    /* If there are more than 1 odd nodes 
    and end of original list is odd then 
    move this node to end to maintain 
    same order of odd numbers in modified list */
    if (new_end != end && (end->data) % 2 != 0) 
    { 
        prev->next = end->next; 
        end->next = NULL; 
        new_end->next = end; 
    } 
    return; 
} 
  
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning */
void push(Node** head_ref, int new_data) 
{ 
    /* allocate node */
    Node* new_node = new Node();
  
    /* put in the data */
    new_node->data = new_data; 
  
    /* link the old list off the new node */
    new_node->next = (*head_ref); 
  
    /* move the head to point to the new node */
    (*head_ref) = new_node; 
} 
  
/* Function to print nodes in a given linked list */
void printList(Node *node) 
{ 
    while (node != NULL) 
    { 
        cout << node->data <<" "; 
        node = node->next; 
    } 
} 
  
/* Driver code*/
int main() 
{ 
    /* Start with the empty list */
    Node* head = NULL; 
  
    /* Let us create a sample linked list as following 
    0->2->4->6->8->10->11 */
  
    push(&head, 11); 
    push(&head, 10); 
    push(&head, 8); 
    push(&head, 6); 
    push(&head, 4); 
    push(&head, 2); 
    push(&head, 0); 
  
    cout << "Original Linked list "; 
    printList(head); 
  
    segregateEvenOdd(&head); 
  
    cout << "\nModified Linked list "; 
    printList(head); 
  
    return 0; 
} 
  
// This code is contributed by rathbhupendra

C

// C program to segregate even and odd nodes in a
// Linked List
#include <stdio.h>
#include <stdlib.h>
  
/* a node of the singly linked list */
struct Node
{
    int data;
    struct Node *next;
};
  
void segregateEvenOdd(struct Node **head_ref)
{
    struct Node *end = *head_ref;
    struct Node *prev = NULL;
    struct Node *curr = *head_ref;
  
    /* Get pointer to the last node */
    while (end->next != NULL)
        end = end->next;
  
    struct Node *new_end = end;
  
    /* Consider all odd nodes before the first even node
       and move then after end */
    while (curr->data %2 != 0 && curr != end)
    {
        new_end->next = curr;
        curr = curr->next;
        new_end->next->next = NULL;
        new_end = new_end->next;
    }
  
    // 10->8->17->17->15
    /* Do following steps only if there is any even node */
    if (curr->data%2 == 0)
    {
        /* Change the head pointer to point to first even node */
        *head_ref = curr;
  
        /* now current points to the first even node */
        while (curr != end)
        {
            if ( (curr->data)%2 == 0 )
            {
                prev = curr;
                curr = curr->next;
            }
            else
            {
                /* break the link between prev and current */
                prev->next = curr->next;
  
                /* Make next of curr as NULL  */
                curr->next = NULL;
  
                /* Move curr to end */
                new_end->next = curr;
  
                /* make curr as new end of list */
                new_end = curr;
  
                /* Update current pointer to next of the moved node */
                curr = prev->next;
            }
        }
    }
  
    /* We must have prev set before executing lines following this
       statement */
    else prev = curr;
  
    /* If there are more than 1 odd nodes and end of original list is
      odd then move this node to end to maintain same order of odd
      numbers in modified list */
    if (new_end!=end && (end->data)%2 != 0)
    {
        prev->next = end->next;
        end->next = NULL;
        new_end->next = end;
    }
    return;
}
  
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning  */
void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node =
        (struct Node*) malloc(sizeof(struct Node));
  
    /* put in the data  */
    new_node->data  = new_data;
  
    /* link the old list off the new node */
    new_node->next = (*head_ref);
  
    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}
  
/* Function to print nodes in a given linked list */
void printList(struct Node *node)
{
    while (node!=NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}
  
/* Driver program to test above functions*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
  
    /* Let us create a sample linked list as following
      0->2->4->6->8->10->11 */
  
    push(&head, 11);
    push(&head, 10);
    push(&head, 8);
    push(&head, 6);
    push(&head, 4);
    push(&head, 2);
    push(&head, 0);
  
    printf("\nOriginal Linked list \n");
    printList(head);
  
    segregateEvenOdd(&head);
  
    printf("\nModified Linked list \n");
    printList(head);
  
    return 0;
}

Java

// Java program to segregate even and odd nodes in a
// Linked List
class LinkedList
{
    Node head;  // head of list
  
    /* Linked list Node*/
    class Node
    {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
  
    void segregateEvenOdd()
    {
        Node end = head;
        Node prev = null;
        Node curr = head;
  
        /* Get pointer to last Node */
        while (end.next != null)
            end = end.next;
  
        Node new_end = end;
  
        // Consider all odd nodes before getting first even node
        while (curr.data %2 !=0 && curr != end)
        {
            new_end.next = curr;
            curr = curr.next;
            new_end.next.next = null;
            new_end = new_end.next;
        }
  
        // do following steps only if there is an even node
        if (curr.data %2 ==0)
        {
            head = curr;
  
            // now curr points to first even node
            while (curr != end)
            {
                if (curr.data % 2 == 0)
                {
                    prev = curr;
                    curr = curr.next;
                }
                else
                {
                    /* Break the link between prev and curr*/
                    prev.next = curr.next;
  
                    /* Make next of curr as null */
                    curr.next = null;
  
                    /*Move curr to end */
                    new_end.next = curr;
  
                    /*Make curr as new end of list */
                    new_end = curr;
  
                    /*Update curr pointer */
                    curr = prev.next;
                }
            }
        }
  
        /* We have to set prev before executing rest of this code */
        else prev = curr;
  
        if (new_end != end && end.data %2 != 0)
        {
            prev.next = end.next;
            end.next = null;
            new_end.next = end;
        }
    }
  
    /*  Given a reference (pointer to pointer) to the head
        of a list and an int, push a new node on the front
        of the list. */
    void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                  Put in the data*/
        Node new_node = new Node(new_data);
  
        /* 3. Make next of new Node as head */
        new_node.next = head;
  
        /* 4. Move the head to point to new Node */
        head = new_node;
    }
  
    // Utility function to print a linked list
    void printList()
    {
        Node temp = head;
        while(temp != null)
        {
            System.out.print(temp.data+" ");
            temp = temp.next;
        }
        System.out.println();
    }
  
  
    /* Driver program to test above functions */
    public static void main(String args[])
    {
        LinkedList llist = new LinkedList();
        llist.push(11);
        llist.push(10);
        llist.push(8);
        llist.push(6);
        llist.push(4);
        llist.push(2);
        llist.push(0);
        System.out.println("Original Linked List");
        llist.printList();
  
        llist.segregateEvenOdd();
  
        System.out.println("Modified Linked List");
        llist.printList();
    }
} /* This code is contributed by Rajat Mishra */

Python

# Python program to segregate even and odd nodes in a
# Linked List
head = None # head of list
  
# Node class 
class Node: 
      
    # Function to initialise the node object 
    def __init__(self, data): 
        self.data = data # Assign data 
        self.next =None
  
def segregateEvenOdd():
  
    global head
    end = head
    prev = None
    curr = head
  
    # Get pointer to last Node 
    while (end.next != None):
        end = end.next
  
    new_end = end
  
    # Consider all odd nodes before getting first even node
    while (curr.data % 2 !=0 and curr != end):
          
        new_end.next = curr
        curr = curr.next
        new_end.next.next = None
        new_end = new_end.next
          
    # do following steps only if there is an even node
    if (curr.data % 2 == 0):
          
        head = curr
  
        # now curr points to first even node
        while (curr != end):
              
            if (curr.data % 2 == 0):
                  
                prev = curr
                curr = curr.next
                  
            else:
                  
                # Break the link between prev and curr
                prev.next = curr.next
  
                # Make next of curr as None 
                curr.next = None
  
                # Move curr to end 
                new_end.next = curr
  
                # Make curr as new end of list 
                new_end = curr
  
                # Update curr pointer 
                curr = prev.next
              
    # We have to set prev before executing rest of this code 
    else:
        prev = curr
  
    if (new_end != end and end.data % 2 != 0):
          
        prev.next = end.next
        end.next = None
        new_end.next = end
          
# Given a reference (pointer to pointer) to the head
# of a list and an int, push a new node on the front
# of the list. 
def push(new_data):
    global head
  
    # 1 & 2: Allocate the Node &
    #         Put in the data
    new_node = Node(new_data)
  
    # 3. Make next of new Node as head 
    new_node.next = head
  
    # 4. Move the head to point to new Node 
    head = new_node
  
# Utility function to print a linked list
def printList():
    global head
    temp = head
    while(temp != None):
          
        print(temp.data, end = " ")
        temp = temp.next
          
    print(" ")
  
# Driver program to test above functions 
  
push(11)
push(10)
push(8)
push(6)
push(4)
push(2)
push(0)
print("Original Linked List")
printList()
  
segregateEvenOdd()
  
print("Modified Linked List")
printList()
  
# This code is contributed by Arnab Kundu 

C#

// C# program to segregate even and odd nodes in a
// Linked List
using System;
  
public class LinkedList
{
    Node head; // head of list
  
    /* Linked list Node*/
    public class Node
    {
        public int data;
        public Node next;
        public Node(int d)
        {
            data = d;
            next = null;
        }
    }
  
    void segregateEvenOdd()
    {
        Node end = head;
        Node prev = null;
        Node curr = head;
  
        /* Get pointer to last Node */
        while (end.next != null)
            end = end.next;
  
        Node new_end = end;
  
        // Consider all odd nodes before 
        // getting first even node
        while (curr.data % 2 != 0 && curr != end)
        {
            new_end.next = curr;
            curr = curr.next;
            new_end.next.next = null;
            new_end = new_end.next;
        }
  
        // do following steps only 
        // if there is an even node
        if (curr.data % 2 == 0)
        {
            head = curr;
  
            // now curr points to first even node
            while (curr != end)
            {
                if (curr.data % 2 == 0)
                {
                    prev = curr;
                    curr = curr.next;
                }
                else
                {
                    /* Break the link between prev and curr*/
                    prev.next = curr.next;
  
                    /* Make next of curr as null */
                    curr.next = null;
  
                    /*Move curr to end */
                    new_end.next = curr;
  
                    /*Make curr as new end of list */
                    new_end = curr;
  
                    /*Update curr pointer */
                    curr = prev.next;
                }
            }
        }
  
        /* We have to set prev before 
        executing rest of this code */
        else prev = curr;
  
        if (new_end != end && end.data % 2 != 0)
        {
            prev.next = end.next;
            end.next = null;
            new_end.next = end;
        }
    }
  
    /* Given a reference (pointer to pointer) to the head
        of a list and an int, push a new node on the front
        of the list. */
    void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                Put in the data*/
        Node new_node = new Node(new_data);
  
        /* 3. Make next of new Node as head */
        new_node.next = head;
  
        /* 4. Move the head to point to new Node */
        head = new_node;
    }
  
    // Utility function to print a linked list
    void printList()
    {
        Node temp = head;
        while(temp != null)
        {
            Console.Write(temp.data + " ");
            temp = temp.next;
        }
        Console.WriteLine();
    }
  
  
    /* Driver code */
    public static void Main(String []args)
    {
        LinkedList llist = new LinkedList();
        llist.push(11);
        llist.push(10);
        llist.push(8);
        llist.push(6);
        llist.push(4);
        llist.push(2);
        llist.push(0);
        Console.WriteLine("Original Linked List");
        llist.printList();
  
        llist.segregateEvenOdd();
  
        Console.WriteLine("Modified Linked List");
        llist.printList();
    }
}
  
// This code has been contributed by 29AjayKumar

Javascript

<script>
// javascript program to segregate even and odd nodes in a
// Linked List
var head; // head of list
  
    /* Linked list Node */
     class Node {
            constructor(val) {
                this.data = val;
                this.next = null;
            }
        }
  
    function segregateEvenOdd() {
        var end = head;
        var prev = null;
        var curr = head;
  
        /* Get pointer to last Node */
        while (end.next != null)
            end = end.next;
  
        var new_end = end;
  
        // Consider all odd nodes before getting first even node
        while (curr.data % 2 != 0 && curr != end) {
            new_end.next = curr;
            curr = curr.next;
            new_end.next.next = null;
            new_end = new_end.next;
        }
  
        // do following steps only if there is an even node
        if (curr.data % 2 == 0) {
            head = curr;
  
            // now curr points to first even node
            while (curr != end) {
                if (curr.data % 2 == 0) {
                    prev = curr;
                    curr = curr.next;
                } else {
                    /* Break the link between prev and curr */
                    prev.next = curr.next;
  
                    /* Make next of curr as null */
                    curr.next = null;
  
                    /* Move curr to end */
                    new_end.next = curr;
  
                    /* Make curr as new end of list */
                    new_end = curr;
  
                    /* Update curr pointer */
                    curr = prev.next;
                }
            }
        }
  
        /* We have to set prev before executing rest of this code */
        else
            prev = curr;
  
        if (new_end != end && end.data % 2 != 0) {
            prev.next = end.next;
            end.next = null;
            new_end.next = end;
        }
    }
  
    /*
     * Given a reference (pointer to pointer) to the head of a list and an int, push
     * a new node on the front of the list.
     */
    function push(new_data) {
        /*
         * 1 & 2: Allocate the Node & Put in the data
         */
        var new_node = new Node(new_data);
  
        /* 3. Make next of new Node as head */
        new_node.next = head;
  
        /* 4. Move the head to point to new Node */
        head = new_node;
    }
  
    // Utility function to print a linked list
    function printList() {
        var temp = head;
        while (temp != null) {
            document.write(temp.data + " ");
            temp = temp.next;
        }
        document.write();
    }
  
    /* Driver program to test above functions */
      
        push(11);
        push(10);
        push(8);
        push(6);
        push(4);
        push(2);
        push(0);
        document.write("Original Linked List ");
        printList();
        document.write("<br>");
  
  
        segregateEvenOdd();
  
        document.write("Modified Linked List ");
  
// This code contributed by umadevi9616
</script>

Producción: 
 

 Original Linked list 0 2 4 6 8 10 11
 Modified Linked list 0 2 4 6 8 10 11

Complete Interview Preparation - GFG

Complejidad temporal: O(n)
Método 2 
La idea es dividir la lista enlazada en dos: una que contenga todos los Nodes pares y otra que contenga todos los Nodes impares. Y finalmente, adjunte la lista vinculada de Nodes impares después de la lista vinculada de Nodes pares. 
Para dividir la Lista vinculada, recorra la Lista vinculada original y mueva todos los Nodes impares a una Lista vinculada separada de todos los Nodes impares. Al final del ciclo, la lista original tendrá todos los Nodes pares y la lista de Nodes impares tendrá todos los Nodes impares. Para mantener el mismo orden de todos los Nodes, debemos insertar todos los Nodes impares al final de la lista de Nodes impares. Y para hacerlo en tiempo constante, debemos realizar un seguimiento del último puntero en la lista de Nodes impares.
 

C++

// CPP program to segregate even and odd nodes in a
// Linked List
#include <bits/stdc++.h>
using namespace std;
  
/* a node of the singly linked list */
struct Node {
    int data;
    struct Node* next;
};
  
// Function to segregate even and odd nodes.
void segregateEvenOdd(struct Node** head_ref)
{
    // Starting node of list having even values.
    Node* evenStart = NULL;
    // Ending node of even values list.
    Node* evenEnd = NULL;
    // Starting node of odd values list.
    Node* oddStart = NULL;
    // Ending node of odd values list.
    Node* oddEnd = NULL;
    // Node to traverse the list.
    Node* currNode = *head_ref;
  
    while (currNode != NULL) {
        int val = currNode->data;
  
        // If current value is even, add it to even values
        // list.
        if (val % 2 == 0) {
            if (evenStart == NULL) {
                evenStart = currNode;
                evenEnd = evenStart;
            }
            else {
                evenEnd->next = currNode;
                evenEnd = evenEnd->next;
            }
        }
  
        // If current value is odd, add it to odd values
        // list.
        else {
            if (oddStart == NULL) {
                oddStart = currNode;
                oddEnd = oddStart;
            }
            else {
                oddEnd->next = currNode;
                oddEnd = oddEnd->next;
            }
        }
  
        // Move head pointer one step in forward direction
        currNode = currNode->next;
    }
  
    // If either odd list or even list is empty, no change
    // is required as all elements are either even or odd.
    if (oddStart == NULL || evenStart == NULL)
        return;
  
    // Add odd list after even list.
    evenEnd->next = oddStart;
    oddEnd->next = NULL;
  
    // Modify head pointer to starting of even list.
    *head_ref = evenStart;
}
  
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning */
void push(Node** head_ref, int new_data)
{
    /* allocate node */
    Node* new_node = new Node();
    /* put in the data */
    new_node->data = new_data;
    /* link the old list off the new node */
    new_node->next = (*head_ref);
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
  
/* Function to print nodes in a given linked list */
void printList(Node* node)
{
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}
  
/* Driver program to test above functions*/
int main()
{
    /* Start with the empty list */
    Node* head = NULL;
  
    /* Let us create a sample linked list as following
    0->1->4->6->9->10->11 */
  
    push(&head, 11);
    push(&head, 10);
    push(&head, 9);
    push(&head, 6);
    push(&head, 4);
    push(&head, 1);
    push(&head, 0);
  
    cout << "Original Linked list" << endl;
    printList(head);
  
    segregateEvenOdd(&head);
  
    cout << endl << "Modified Linked list " << endl;
    printList(head);
  
    return 0;
}
  
// This code is contributed by Aditya Kumar (adityakumar129)

C

// C program to segregate even and odd nodes in a
// Linked List
#include <stdio.h>
#include <stdlib.h>
  
/* a node of the singly linked list */
typedef struct Node {
    int data;
    struct Node* next;
} Node;
  
// Function to segregate even and odd nodes.
void segregateEvenOdd(Node** head_ref)
{
    // Starting node of list having
    // even values.
    Node* evenStart = NULL;
    // Ending node of even values list.
    Node* evenEnd = NULL;
    // Starting node of odd values list.
    Node* oddStart = NULL;
    // Ending node of odd values list.
    Node* oddEnd = NULL;
    // Node to traverse the list.
    Node* currNode = *head_ref;
  
    while (currNode != NULL) {
        int val = currNode->data;
  
        // If current value is even, add it to even values
        // list.
        if (val % 2 == 0) {
            if (evenStart == NULL) {
                evenStart = currNode;
                evenEnd = evenStart;
            }
            else {
                evenEnd->next = currNode,
                evenEnd = evenEnd->next;
            }
        }
  
        // If current value is odd, add it to odd values
        // list.
        else {
            if (oddStart == NULL) {
                oddStart = currNode;
                oddEnd = oddStart;
            }
            else {
                oddEnd->next = currNode;
                oddEnd = oddEnd->next;
            }
        }
  
        // Move head pointer one step in forward direction
        currNode = currNode->next;
    }
  
    // If either odd list or even list is empty, no change
    // is required as all elements are either even or odd.
    if (oddStart == NULL || evenStart == NULL)
        return;
  
    // Add odd list after even list.
    evenEnd->next = oddStart;
    oddEnd->next = NULL;
  
    // Modify head pointer to
    // starting of even list.
    *head_ref = evenStart;
}
  
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning */
void push(Node** head_ref, int new_data)
{
    /* allocate node */
    Node* new_node = (Node*)malloc(sizeof(Node));
    /* put in the data */
    new_node->data = new_data;
    /* link the old list off the new node */
    new_node->next = (*head_ref);
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
  
/* Function to print nodes in a given linked list */
void printList(Node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}
  
/* Driver program to test above functions*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
  
    /* Let us create a sample linked list as following
    0->1->4->6->9->10->11 */
  
    push(&head, 11);
    push(&head, 10);
    push(&head, 9);
    push(&head, 6);
    push(&head, 4);
    push(&head, 1);
    push(&head, 0);
  
    printf("\nOriginal Linked list \n");
    printList(head);
  
    segregateEvenOdd(&head);
  
    printf("\nModified Linked list \n");
    printList(head);
  
    return 0;
}
  
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java program to segregate even and odd nodes in a
// Linked List
import java.io.*;
  
class LinkedList {
      
    Node head;  // head of list
   
    /* Linked list Node*/
    class Node
    {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
      
    public void segregateEvenOdd() {
          
        Node evenStart = null;
        Node evenEnd = null;
        Node oddStart = null;
        Node oddEnd = null;
        Node currentNode = head;
          
        while(currentNode != null) {
            int element = currentNode.data;
              
            if(element % 2 == 0) {
                  
                if(evenStart == null) {
                    evenStart = currentNode;
                    evenEnd = evenStart;
                } else {
                    evenEnd.next = currentNode;
                    evenEnd = evenEnd.next;
                }
                  
            } else {
                  
                if(oddStart == null) {
                    oddStart = currentNode;
                    oddEnd = oddStart;
                } else {
                    oddEnd.next = currentNode;
                    oddEnd = oddEnd.next;
                }
            }
                        // Move head pointer one step in forward direction
            currentNode = currentNode.next;    
        }
          
          
        if(oddStart == null || evenStart == null) {
            return;
        }
          
        evenEnd.next = oddStart;
        oddEnd.next = null;
        head=evenStart;
    }
      
    /*  Given a reference (pointer to pointer) to the head
        of a list and an int, push a new node on the front
        of the list. */
    void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                  Put in the data*/
        Node new_node = new Node(new_data);
   
        /* 3. Make next of new Node as head */
        new_node.next = head;
   
        /* 4. Move the head to point to new Node */
        head = new_node;
    }
   
    // Utility function to print a linked list
    void printList()
    {
        Node temp = head;
        while(temp != null)
        {
            System.out.print(temp.data+" ");
            temp = temp.next;
        }
        System.out.println();
    }
      
    /* Driver program to test above functions */
    public static void main(String args[])
    {
        LinkedList llist = new LinkedList();
        llist.push(11);
        llist.push(10);
        llist.push(9);
        llist.push(6);
        llist.push(4);
        llist.push(1);
        llist.push(0);
        System.out.println("Original Linked List");
        llist.printList();
   
        llist.segregateEvenOdd();
   
        System.out.println("Modified Linked List");
        llist.printList();
    }
}

C#

// C# program to segregate even and odd nodes in a
// Linked List
using System;
      
public class LinkedList
{
      
    Node head; // head of list
  
    /* Linked list Node*/
    public class Node
    {
        public int data;
        public Node next;
        public Node(int d)
        {
            data = d;
            next = null;
        }
    }
      
    public void segregateEvenOdd() 
    {
          
        Node evenStart = null;
        Node evenEnd = null;
        Node oddStart = null;
        Node oddEnd = null;
        Node currentNode = head;
          
        while(currentNode != null) 
        {
            int element = currentNode.data;
              
            if(element % 2 == 0) 
            {
                  
                if(evenStart == null) 
                {
                    evenStart = currentNode;
                    evenEnd = evenStart;
                }
                else
                {
                    evenEnd.next = currentNode;
                    evenEnd = evenEnd.next;
                }
                  
            } 
            else
            {
                  
                if(oddStart == null)
                {
                    oddStart = currentNode;
                    oddEnd = oddStart;
                }
                else
                {
                    oddEnd.next = currentNode;
                    oddEnd = oddEnd.next;
                }
            }
          
        // Move head pointer one step in forward direction
            currentNode = currentNode.next; 
        }
          
          
        if(oddStart == null || evenStart == null)
        {
            return;
        }
          
        evenEnd.next = oddStart;
        oddEnd.next = null;
        head=evenStart;
    }
      
    /* Given a reference (pointer to pointer) to the head
        of a list and an int, push a new node on the front
        of the list. */
    void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                Put in the data*/
        Node new_node = new Node(new_data);
  
        /* 3. Make next of new Node as head */
        new_node.next = head;
  
        /* 4. Move the head to point to new Node */
        head = new_node;
    }
  
    // Utility function to print a linked list
    void printList()
    {
        Node temp = head;
        while(temp != null)
        {
            Console.Write(temp.data+" ");
            temp = temp.next;
        }
        Console.WriteLine();
    }
      
    /* Driver code */
    public static void Main()
    {
        LinkedList llist = new LinkedList();
        llist.push(11);
        llist.push(10);
        llist.push(9);
        llist.push(6);
        llist.push(4);
        llist.push(1);
        llist.push(0);
        Console.WriteLine("Original Linked List");
        llist.printList();
  
        llist.segregateEvenOdd();
  
        Console.WriteLine("Modified Linked List");
        llist.printList();
    }
}
  
/* This code contributed by PrinciRaj1992 */

Python3

# Python3 program to segregate even and odd nodes in a
# Linked List
head = None # head of list 
  
# Node class  
class Node:  
        
    # Function to initialise the node object  
    def __init__(self, data):  
        self.data = data # Assign data  
        self.next =None
  
# Function to segregate even and odd nodes.
def segregateEvenOdd():
    global head 
      
    # Starting node of list having 
    # even values.
    evenStart = None
      
    # Ending node of even values list.
    evenEnd = None
      
    # Starting node of odd values list.
    oddStart = None
      
    # Ending node of odd values list.
    oddEnd = None
      
    # Node to traverse the list.
    currNode = head
      
    while(currNode != None):
        val = currNode.data
          
        # If current value is even, add
        # it to even values list.
        if(val % 2 == 0):
            if(evenStart == None):
                evenStart = currNode
                evenEnd = evenStart
            else:
                evenEnd . next = currNode
                evenEnd = evenEnd . next
          
        # If current value is odd, add 
        # it to odd values list.
        else:
            if(oddStart == None):
                oddStart = currNode
                oddEnd = oddStart
            else:
                oddEnd . next = currNode
                oddEnd = oddEnd . next
                  
        # Move head pointer one step in 
        # forward direction
        currNode = currNode . next 
      
    # If either odd list or even list is empty,
    # no change is required as all elements 
    # are either even or odd.
    if(oddStart == None or evenStart == None):
        return
      
    # Add odd list after even list.     
    evenEnd . next = oddStart
    oddEnd . next = None
      
    # Modify head pointer to 
    # starting of even list.
    head = evenStart
  
''' UTILITY FUNCTIONS '''
''' Function to insert a node at the beginning '''
def push(new_data):
      
    global head 
    # 1 & 2: Allocate the Node & 
    #         Put in the data 
    new_node = Node(new_data) 
      
    # 3. Make next of new Node as head  
    new_node.next = head 
      
    # 4. Move the head to point to new Node  
    head = new_node 
  
''' Function to print nodes in a given linked list '''
def printList():
    global head
    node = head
    while (node != None):
        print(node.data, end = " ")
        node = node.next
    print()
      
''' Driver program to test above functions'''
  
''' Let us create a sample linked list as following
0.1.4.6.9.10.11 '''
  
push(11)
push(10)
push(9)
push(6)
push(4)
push(1)
push(0)
  
print("Original Linked list")
printList()
  
segregateEvenOdd()
  
print("Modified Linked list")
printList()
  
# This code is contributed by shubhamsingh10.

Javascript

<script>
  
// JavaScript program to segregate 
// even and odd nodes in a
// Linked List
      
    var head;  // head of list
   
    /* Linked list Node*/
    class Node {
        constructor(val) {
            this.data = val;
            this.next = null;
        }
    }
      
     function segregateEvenOdd() {
          
        var evenStart = null;
        var evenEnd = null;
        var oddStart = null;
        var oddEnd = null;
        var currentNode = head;
          
        while(currentNode != null) {
            var element = currentNode.data;
              
            if(element % 2 == 0) {
                  
                if(evenStart == null) {
                    evenStart = currentNode;
                    evenEnd = evenStart;
                } else {
                    evenEnd.next = currentNode;
                    evenEnd = evenEnd.next;
                }
                  
            } else {
                  
                if(oddStart == null) {
                    oddStart = currentNode;
                    oddEnd = oddStart;
                } else {
                    oddEnd.next = currentNode;
                    oddEnd = oddEnd.next;
                }
            }
                        // Move head pointer one 
                        // step in forward direction
            currentNode = currentNode.next;    
        }
          
          
        if(oddStart == null || evenStart == null) {
            return;
        }
          
        evenEnd.next = oddStart;
        oddEnd.next = null;
        head=evenStart;
    }
      
    /*  Given a reference (pointer to pointer) to the head
        of a list and an int, push a new node on the front
        of the list. */
    function push(new_data)
    {
        /* 1 & 2: Allocate the Node &
                  Put in the data*/
        var new_node = new Node(new_data);
   
        /* 3. Make next of new Node as head */
        new_node.next = head;
   
        /* 4. Move the head to point to new Node */
        head = new_node;
    }
   
    // Utility function to print a linked list
    function printList()
    {
        var temp = head;
        while(temp != null)
        {
            document.write(temp.data+" ");
            temp = temp.next;
        }
        document.write("<br/>");
    }
      
    /* Driver program to test above functions */
      
        push(11);
        push(10);
        push(9);
        push(6);
        push(4);
        push(1);
        push(0);
        document.write("Original Linked List<br/>");
        printList();
   
        segregateEvenOdd();
   
        document.write("Modified Linked List<br/>");
        printList();
  
// This code is contributed by todaysgaurav
  
</script>

Producción:  

Original Linked List
0 1 4 6 9 10 11 
Modified Linked List
0 4 6 10 1 9 11 

Complejidad de tiempo: O(n)
Escriba comentarios si encuentra que el código/algoritmo anterior es incorrecto o encuentra otras formas de resolver el mismo problema.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *