Suponga que la estructura de un Node de lista enlazada es la siguiente.
C++
struct Node
{
int data;
struct Node *next;
};
// This code is contributed by SHUBHAMSINGH10
C
struct Node
{
int data;
struct Node *next;
};
Java
static class Node
{
int data;
Node next;
};
// This code is contributed by shubhamsingh10
Python3
class Node: def __init__(self, data): self.data = data self.next = None
C#
public class Node
{
public int data;
public Node next;
};
// This code is contributed by pratham_76
Javascript
<script>
class Node
{
constructor(item)
{
this.data = item;
this.next = null;
}
}
// This code contributed by shubhamsingh10
</script>
Explique la funcionalidad de las siguientes funciones de C.
1. ¿Qué hace la siguiente función para una lista enlazada dada?
C++14
void fun1(struct Node* head)
{
if (head == NULL)
return;
fun1(head->next);
cout << head->data << " ";
}
// This code is contributed by shubhamsingh10
C
void fun1(struct Node* head)
{
if(head == NULL)
return;
fun1(head->next);
printf("%d ", head->data);
}
Java
static void fun1(Node head)
{
if (head == null)
{
return;
}
fun1(head.next);
System.out.print(head.data + " ");
}
// This code is contributed by shubhamsingh10
Python
def fun1(head): if(head == None): return fun1(head.next) print(head.data, end = " ") # This code is contributed by shubhamsingh10
C#
static void fun1(Node head)
{
if (head == null)
{
return;
}
fun1(head.next);
Console.Write(head.data + " ");
}
// This code is contributed by shubhamsingh10
Javascript
<script>
// Javascript Implementation
function fun1( head)
{
if (head == null)
return;
fun1(head.next);
document.write(head.data);
}
// This code is contributed by shubhamsingh10
</script>
fun1() imprime la lista enlazada dada de forma inversa. Para Lista enlazada 1->2->3->4->5, fun1() imprime 5->4->3->2->1.
2. ¿Qué hace la siguiente función para una lista enlazada dada?
C++
void fun2(struct Node* head)
{
if(head == NULL)
return;
cout << head->data << " ";
if(head->next != NULL )
fun2(head->next->next);
cout << head->data << " ";
}
// This code is contributed by shubhamsingh10
C
void fun2(struct Node* head)
{
if(head == NULL)
return;
printf("%d ", head->data);
if(head->next != NULL )
fun2(head->next->next);
printf("%d ", head->data);
}
Java
static void fun2(Node head)
{
if (head == null)
{
return;
}
System.out.print(head.data + " ");
if (head.next != null)
{
fun2(head.next.next);
}
System.out.print(head.data + " ");
}
// This code is contributed by shubhamsingh10
Python3
def fun2(head): if(head == None): return print(head.data, end = " ") if(head.next != None ): fun2(head.next.next) print(head.data, end = " ") # This code is contributed by divyesh072019
C#
static void fun2(Node head)
{
if (head == null)
{
return;
}
Console.Write(head.data + " ");
if (head.next != null)
{
fun2(head.next.next);
}
Console.Write(head.data + " ");
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript Implementation
function fun2( head)
{
if (head == null)
return;
document.write(head.data);
if (head.next != null)
fun2(head.next.next);
document.write(head.data);
}
// This code is contributed by shubhamsingh10
</script>
fun2() imprime Nodes alternativos de la lista enlazada dada, primero de principio a fin y luego de principio a fin. Si la lista enlazada tiene un número par de Nodes, entonces fun2() omite el último Node. Para Lista enlazada 1->2->3->4->5, fun2() imprime 1 3 5 5 3 1. Para Lista enlazada 1->2->3->4->5->6, fun2( ) imprime 1 3 5 5 3 1.
A continuación se muestra un programa en ejecución completo para probar las funciones anteriores.
C++
#include <bits/stdc++.h>
using namespace std;
/* A linked list node */
class Node
{
public:
int data;
Node *next;
};
/* Prints a linked list in reverse manner */
void fun1(Node* head)
{
if(head == NULL)
return;
fun1(head->next);
cout << head->data << " ";
}
/* prints alternate nodes of a Linked List, first
from head to end, and then from end to head. */
void fun2(Node* start)
{
if(start == NULL)
return;
cout<<start->data<<" ";
if(start->next != NULL )
fun2(start->next->next);
cout << start->data << " ";
}
/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* 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(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;
}
/* Driver code */
int main()
{
/* Start with the empty list */
Node* head = NULL;
/* Using push() to construct below list
1->2->3->4->5 */
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout<<"Output of fun1() for list 1->2->3->4->5 \n";
fun1(head);
cout<<"\nOutput of fun2() for list 1->2->3->4->5 \n";
fun2(head);
return 0;
}
// This code is contributed by rathbhupendra
C
#include<stdio.h>
#include<stdlib.h>
/* A linked list node */
struct Node
{
int data;
struct Node *next;
};
/* Prints a linked list in reverse manner */
void fun1(struct Node* head)
{
if(head == NULL)
return;
fun1(head->next);
printf("%d ", head->data);
}
/* prints alternate nodes of a Linked List, first
from head to end, and then from end to head. */
void fun2(struct Node* start)
{
if(start == NULL)
return;
printf("%d ", start->data);
if(start->next != NULL )
fun2(start->next->next);
printf("%d ", start->data);
}
/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* 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)
{
/* 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;
}
/* Driver program to test above functions */
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
/* Using push() to construct below list
1->2->3->4->5 */
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
printf("Output of fun1() for list 1->2->3->4->5 \n");
fun1(head);
printf("\nOutput of fun2() for list 1->2->3->4->5 \n");
fun2(head);
getchar();
return 0;
}
Java
// Java code implementation for above approach
class GFG
{
/* A linked list node */
static class Node
{
int data;
Node next;
};
/* Prints a linked list in reverse manner */
static void fun1(Node head)
{
if (head == null)
{
return;
}
fun1(head.next);
System.out.print(head.data + " ");
}
/* prints alternate nodes of a Linked List, first
from head to end, and then from end to head. */
static void fun2(Node start)
{
if (start == null)
{
return;
}
System.out.print(start.data + " ");
if (start.next != null)
{
fun2(start.next.next);
}
System.out.print(start.data + " ");
}
/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* 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)
{
/* 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;
return head_ref;
}
/* Driver code */
public static void main(String[] args)
{
/* Start with the empty list */
Node head = null;
/* Using push() to construct below list
1->2->3->4->5 */
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
System.out.print("Output of fun1() for " +
"list 1->2->3->4->5 \n");
fun1(head);
System.out.print("\nOutput of fun2() for " +
"list 1->2->3->4->5 \n");
fun2(head);
}
}
// This code is contributed by Rajput-Ji
Python3
''' A linked list node '''
class Node:
def __init__(self, data):
self.data = data
self.next = None
''' Prints a linked list in reverse manner '''
def fun1(head):
if(head == None):
return
fun1(head.next)
print(head.data, end = " ")
''' prints alternate nodes of a Linked List, first
from head to end, and then from end to head. '''
def fun2(start):
if(start == None):
return
print(start.data, end = " ")
if(start.next != None ):
fun2(start.next.next)
print(start.data, end = " ")
''' UTILITY FUNCTIONS TO TEST fun1() and fun2() '''
''' 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, new_data):
''' put in the data '''
new_node = Node(new_data)
''' link the old list off the new node '''
new_node.next = head
''' move the head to point to the new node '''
head = new_node
return head
''' Driver code '''
''' Start with the empty list '''
head = None
''' Using push() to construct below list
1.2.3.4.5 '''
head = Node(5)
head = push(head, 4)
head = push(head, 3)
head = push(head, 2)
head = push(head, 1)
print("Output of fun1() for list 1->2->3->4->5")
fun1(head)
print("\nOutput of fun2() for list 1->2->3->4->5")
fun2(head)
# This code is contributed by SHUBHAMSINGH10
C#
// C# code implementation for above approach
using System;
class GFG
{
/* A linked list node */
public class Node
{
public int data;
public Node next;
};
/* Prints a linked list in reverse manner */
static void fun1(Node head)
{
if (head == null)
{
return;
}
fun1(head.next);
Console.Write(head.data + " ");
}
/* prints alternate nodes of a Linked List, first
from head to end, and then from end to head. */
static void fun2(Node start)
{
if (start == null)
{
return;
}
Console.Write(start.data + " ");
if (start.next != null)
{
fun2(start.next.next);
}
Console.Write(start.data + " ");
}
/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* 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)
{
/* 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;
return head_ref;
}
/* Driver code */
public static void Main(String[] args)
{
/* Start with the empty list */
Node head = null;
/* Using.Push() to construct below list
1->2->3->4->5 */
head = Push(head, 5);
head = Push(head, 4);
head = Push(head, 3);
head = Push(head, 2);
head = Push(head, 1);
Console.Write("Output of fun1() for " +
"list 1->2->3->4->5 \n");
fun1(head);
Console.Write("\nOutput of fun2() for " +
"list 1->2->3->4->5 \n");
fun2(head);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript code implementation for above approach
/* A linked list node */
class Node
{
constructor(data) {
this.next = null;
this.data = data;
}
}
/* Prints a linked list in reverse manner */
function fun1(head)
{
if (head == null)
{
return;
}
fun1(head.next);
document.write(head.data + " ");
}
/* prints alternate nodes of a Linked List, first
from head to end, and then from end to head. */
function fun2(start)
{
if (start == null)
{
return;
}
document.write(start.data + " ");
if (start.next != null)
{
fun2(start.next.next);
}
document.write(start.data + " ");
}
/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* 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)
{
/* allocate node */
/* put in the data */
let new_node = new Node(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;
return head_ref;
}
/* Start with the empty list */
let head = null;
/* Using.Push() to construct below list
1->2->3->4->5 */
head = Push(head, 5);
head = Push(head, 4);
head = Push(head, 3);
head = Push(head, 2);
head = Push(head, 1);
document.write("Output of fun1() for " +
"list 1->2->3->4->5 " + "</br>");
fun1(head);
document.write("</br>");
document.write("Output of fun2() for " +
"list 1->2->3->4->5 " + "</br>");
fun2(head);
// This code is contributed by mukesh07.
</script>
Producción:
Output of fun1() for list 1->2->3->4->5 5 4 3 2 1 Output of fun2() for list 1->2->3->4->5 1 3 5 5 3 1
Complejidad temporal: O(n)
Espacio Auxiliar: O(1)
Escriba comentarios si encuentra que alguna de las respuestas/explicaciones es incorrecta, o si desea compartir más información sobre los temas discutidos anteriormente.
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