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:
- Obtener puntero al último Node.
- Mueva todos los Nodes impares hasta el final.
- Considere todos los Nodes impares antes del primer Node par y muévalos al final.
- Cambie el puntero principal para que apunte al primer Node par.
- Considere todos los Nodes impares después del primer Node par y muévalos al final.
Javascript
<script>
// Javascript program to segregate even and
// odd nodes in a Linked List
// Head of list
var head;
// 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 eve 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 code
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 is 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
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.
Javascript
<script>
// JavaScript program to segregate
// even and odd nodes in a Linked List
// Head of list
var head;
// 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 code
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)
Consulte el artículo completo sobre Segregación de Nodes pares e impares en una lista enlazada para obtener más detalles.
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