Dada una lista enlazada. la tarea es mover todos los 0 al frente de la lista enlazada. El orden de todos los demás elementos excepto 0 debe ser el mismo después de la reorganización.
Ejemplos:
Input : 0 1 0 1 2 0 5 0 4 0 Output :0 0 0 0 0 1 1 2 5 4 Input :1 1 2 3 0 0 0 Output :0 0 0 1 1 2 3
Una solución simple es almacenar todos los elementos de la lista enlazada en una array. Luego mueva todos los elementos de la array al principio. Finalmente, copie los elementos de la array de nuevo a la lista enlazada.
Una solución eficiente es recorrer la lista enlazada desde el segundo Node. Para cada Node con valor 0, lo desconectamos de su posición actual y movemos el Node al frente.
C++
// CPP program to move all zeros to the end of the linked list.
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
};
// 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(struct Node** head_ref, int new_data)
{
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* moving zeroes to the beginning in linked list */
void moveZeroes(struct Node** head)
{
if (*head == NULL)
return;
// Traverse the list from second node.
struct Node *temp = (*head)->next, *prev = *head;
while (temp != NULL) {
// If current node is 0, move to beginning of linked
// list
if (temp->data == 0) {
// Disconnect node from its
// current position
Node* curr = temp;
temp = temp->next;
prev->next = temp;
// Move to beginning
curr->next = (*head);
*head = curr;
}
// For non-zero values
else {
prev = temp;
temp = temp->next;
}
}
}
// function to displaying nodes
void display(struct Node* head)
{
while (head != NULL) {
cout << head->data << "->";
head = head->next;
}
cout << "NULL";
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
/* Use push() to construct below list
0->0->1->0->1->0->2->0->3->0 */
push(&head, 0);
push(&head, 3);
push(&head, 0);
push(&head, 2);
push(&head, 0);
push(&head, 1);
push(&head, 0);
push(&head, 1);
push(&head, 0);
push(&head, 0);
// displaying list before rearrangement
cout << "Linked list before rearrangement\n";
display(head);
/* Check the move_zeroes function */
moveZeroes(&head);
// displaying list after rearrangement
cout << "\n Linked list after rearrangement \n";
display(head);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to move all zeros to the end of the linked list.
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
typedef struct Node {
int data;
struct Node* next;
}Node;
// 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(struct Node** head_ref, int new_data)
{
struct Node* new_node = (Node *)malloc(sizeof(Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* moving zeroes to the beginning in linked list */
void moveZeroes(struct Node** head)
{
if (*head == NULL)
return;
// Traverse the list from second node.
struct Node *temp = (*head)->next, *prev = *head;
while (temp != NULL) {
// If current node is 0, move to beginning of linked
// list
if (temp->data == 0) {
// Disconnect node from its current position
Node* curr = temp;
temp = temp->next;
prev->next = temp;
// Move to beginning
curr->next = (*head);
*head = curr;
}
// For non-zero values
else {
prev = temp;
temp = temp->next;
}
}
}
// function to displaying nodes
void display(struct Node* head)
{
while (head != NULL) {
printf("%d->",head->data);
head = head->next;
}
printf("NULL");
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
/* Use push() to construct below list
0->0->1->0->1->0->2->0->3->0 */
push(&head, 0);
push(&head, 3);
push(&head, 0);
push(&head, 2);
push(&head, 0);
push(&head, 1);
push(&head, 0);
push(&head, 1);
push(&head, 0);
push(&head, 0);
// displaying list before rearrangement
printf("Linked list before rearrangement\n");
display(head);
/* Check the move_zeroes function */
moveZeroes(&head);
// displaying list after rearrangement
printf("\nLinked list after rearrangement \n");
display(head);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// JAVA program to move all zeros
// to the end of the linked list.
class GFG {
/* Link list node */
static class Node {
int data;
Node next;
};
/* 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. */
static Node push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
return new_node;
}
/* moving zeroes to the beginning in linked list */
static Node moveZeroes(Node head)
{
if (head == null)
return null;
// Traverse the list from second node.
Node temp = (head).next, prev = head;
while (temp != null) {
// If current node is 0, move to
// beginning of linked list
if (temp.data == 0) {
// Disconnect node from its
// current position
Node curr = temp;
temp = temp.next;
prev.next = temp;
// Move to beginning
curr.next = (head);
head = curr;
}
// For non-zero values
else {
prev = temp;
temp = temp.next;
}
}
return head;
}
// function to displaying nodes
static void display(Node head)
{
while (head != null) {
System.out.print(head.data + "->");
head = head.next;
}
System.out.print("null");
}
/* Driver code*/
public static void main(String[] args)
{
/* Start with the empty list */
Node head = null;
/* Use push() to construct below list
0.0.1.0.1.0.2.0.3.0 */
head = push(head, 0);
head = push(head, 3);
head = push(head, 0);
head = push(head, 2);
head = push(head, 0);
head = push(head, 1);
head = push(head, 0);
head = push(head, 1);
head = push(head, 0);
head = push(head, 0);
// displaying list before rearrangement
System.out.print(
"Linked list before rearrangement\n");
display(head);
/* Check the move_zeroes function */
head = moveZeroes(head);
// displaying list after rearrangement
System.out.print(
"\n Linked list after rearrangement \n");
display(head);
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program to move all zeros
# to the end of the linked list.
''' Link list node '''
class Node:
def __init__(self, data):
self.data = data
self.next = None
''' 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(head_ref, new_data):
new_node = Node(new_data)
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref
''' moving zeroes to the beginning in linked list '''
def moveZeroes(head):
if (head == None):
return;
# Traverse the list from second node.
temp = head.next
prev = head;
while (temp != None):
# If current node is 0, move to
# beginning of linked list
if (temp.data == 0):
# Disconnect node from its
# current position
curr = temp;
temp = temp.next;
prev.next = temp;
# Move to beginning
curr.next = (head);
head = curr;
# For non-zero values
else:
prev = temp;
temp = temp.next;
return head
# function to displaying nodes
def display(head):
while (head != None):
print(head.data, end = '->')
head = head.next;
print('NULL', end = '')
''' Driver program to test above function'''
if __name__=='__main__':
''' Start with the empty list '''
head = None;
''' Use push() to construct below list
0.0.1.0.1.0.2.0.3.0 '''
head = push(head, 0);
head = push(head, 3);
head = push(head, 0);
head = push(head, 2);
head = push(head, 0);
head = push(head, 1);
head = push(head, 0);
head = push(head, 1);
head = push(head, 0);
head = push(head, 0);
# displaying list before rearrangement
print("Linked list before rearrangement");
display(head);
''' Check the move_zeroes function '''
head = moveZeroes(head);
# displaying list after rearrangement
print("\n\nLinked list after rearrangement ");
display(head);
# This code is contributed by rutvik_56
C#
// C# program to move all zeros
// to the end of the linked list.
using System;
class GFG
{
/* Link list node */
class Node
{
public int data;
public Node next;
};
/* 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. */
static Node push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
return new_node;
}
/* moving zeroes to the beginning in linked list */
static Node moveZeroes(Node head)
{
if (head == null)
return null;
// Traverse the list from second node.
Node temp = (head).next, prev = head;
while (temp != null)
{
// If current node is 0, move to
// beginning of linked list
if (temp.data == 0)
{
// Disconnect node from its
// current position
Node curr = temp;
temp = temp.next;
prev.next = temp;
// Move to beginning
curr.next = (head);
head = curr;
}
// For non-zero values
else
{
prev = temp;
temp = temp.next;
}
}
return head;
}
// function to displaying nodes
static void display(Node head)
{
while (head != null)
{
Console.Write(head.data + "->");
head = head.next;
}
Console.Write("null");
}
// Driver code
public static void Main(String[] args)
{
/* Start with the empty list */
Node head = null;
/* Use push() to construct below list
0->0->1->0->1->0->2->0->3->0 */
head = push(head, 0);
head = push(head, 3);
head = push(head, 0);
head = push(head, 2);
head = push(head, 0);
head = push(head, 1);
head = push(head, 0);
head = push(head, 1);
head = push(head, 0);
head = push(head, 0);
// displaying list before rearrangement
Console.Write("Linked list before rearrangement\n");
display(head);
/* Check the move_zeroes function */
head = moveZeroes(head);
// displaying list after rearrangement
Console.Write("\n Linked list after rearrangement \n");
display(head);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to move all zeros
// to the end of the linked list.
/* Link list node */
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
};
/* 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(head_ref, new_data)
{
var new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
return new_node;
}
/* moving zeroes to the beginning in linked list */
function moveZeroes(head)
{
if (head == null)
return null;
// Traverse the list from second node.
var temp = (head).next, prev = head;
while (temp != null)
{
// If current node is 0, move to
// beginning of linked list
if (temp.data == 0)
{
// Disconnect node from its
// current position
var curr = temp;
temp = temp.next;
prev.next = temp;
// Move to beginning
curr.next = (head);
head = curr;
}
// For non-zero values
else
{
prev = temp;
temp = temp.next;
}
}
return head;
}
// function to displaying nodes
function display(head)
{
while (head != null)
{
document.write(head.data + "->");
head = head.next;
}
document.write("null");
}
// Driver code
/* Start with the empty list */
var head = null;
/* Use push() to construct below list
0->0->1->0->1->0->2->0->3->0 */
head = push(head, 0);
head = push(head, 3);
head = push(head, 0);
head = push(head, 2);
head = push(head, 0);
head = push(head, 1);
head = push(head, 0);
head = push(head, 1);
head = push(head, 0);
head = push(head, 0);
// displaying list before rearrangement
document.write("Linked list before rearrangement<br>");
display(head);
/* Check the move_zeroes function */
head = moveZeroes(head);
// displaying list after rearrangement
document.write("<br> Linked list after rearrangement <br>");
display(head);
</script>
Producción:
Linked list before rearrangement 0->0->1->0->1->0->2->0->3->0->NULL Linked list after rearrangement 0->0->0->0->0->0->1->1->2->3->NULL
Publicación traducida automáticamente
Artículo escrito por Vishal_Khoda y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA