Imprimir Nodes de lista enlazada en índices dados

Dada una lista de enlaces simples  l1         que está ordenada en orden ascendente y otra lista de enlaces simples  l2         que no está ordenada. La tarea es imprimir los elementos de la segunda lista enlazada según la posición señalada por los datos en los Nodes de la primera lista enlazada. Por ejemplo, si la primera lista enlazada es 1->2->5 , entonces debe imprimir los elementos 1 , 2 y 5 de la segunda lista enlazada .

Ejemplos

Input: l1 = 1->2->5
       l2 = 1->8->7->6->2->9->10
Output : 1->8->2
Elements in l1 are 1, 2 and 5. 
Therefore, print 1st, 2nd and 5th elements of l2,
Which are 1, 8 and 2.

Input: l1 = 2->5 
       l2 = 7->5->3->2->8
Output: 5->8 

Tome dos punteros para recorrer las dos listas vinculadas utilizando dos bucles anidados. El bucle exterior apunta a los elementos de la primera lista y el bucle interior apunta a los elementos de la segunda lista respectivamente. En la primera iteración del ciclo externo, el puntero al encabezado de la primera lista enlazada apunta a su Node raíz. Atravesamos la segunda lista enlazada hasta llegar a la posición señalada por los datos del Node en la primera lista enlazada. Una vez alcanzada la posición requerida, imprima los datos de la segunda lista y repita este proceso nuevamente hasta llegar al final de la primera lista enlazada. 

A continuación se muestra la implementación del enfoque anterior:  

C++

// C++ program to print second linked list
// according to data in the first linked list
#include <iostream>
using namespace std;
  
// Linked List Node
struct Node {
    int data;
    struct Node* next;
};
  
/* Function to insert a node at the beginning */
void push(struct 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;
}
  
// Function to print the second list according
// to the positions referred by the 1st list
void printSecondList(Node* l1, Node* l2)
{
    struct Node* temp = l1;
    struct Node* temp1 = l2;
  
    // While first linked list is not null.
    while (temp != NULL) {
        int i = 1;
  
        // While second linked list is not equal
        // to the data in the node of the
        // first linked list.
        while (i < temp->data) {
            // Keep incrementing second list
            temp1 = temp1->next;
            i++;
        }
  
        // Print the node at position in second list
        // pointed by current element of first list
        cout << temp1->data << " ";
  
        // Increment first linked list
        temp = temp->next;
  
        // Set temp1 to the start of the
        // second linked list
        temp1 = l2;
    }
}
  
// Driver Code
int main()
{
    struct Node *l1 = NULL, *l2 = NULL;
  
    // Creating 1st list
    // 2 -> 5
    push(&l1, 5);
    push(&l1, 2);
  
    // Creating 2nd list
    // 4 -> 5 -> 6 -> 7 -> 8
    push(&l2, 8);
    push(&l2, 7);
    push(&l2, 6);
    push(&l2, 5);
    push(&l2, 4);
  
    printSecondList(l1, l2);
  
    return 0;
}

Java

// Java program to print second linked list 
// according to data in the first linked list 
class GFG
{
      
// Linked List Node 
static class Node
{ 
    int data; 
    Node next; 
}; 
  
/* Function to insert a node at the beginning */
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 head_ref; 
} 
  
// Function to print the second list according 
// to the positions referred by the 1st list 
static void printSecondList(Node l1, Node l2) 
{ 
    Node temp = l1; 
    Node temp1 = l2; 
  
    // While first linked list is not null. 
    while (temp != null)
    { 
        int i = 1; 
  
        // While second linked list is not equal 
        // to the data in the node of the 
        // first linked list. 
        while (i < temp.data) 
        { 
            // Keep incrementing second list 
            temp1 = temp1.next; 
            i++; 
        } 
  
        // Print the node at position in second list 
        // pointed by current element of first list 
        System.out.print( temp1.data + " "); 
  
        // Increment first linked list 
        temp = temp.next; 
  
        // Set temp1 to the start of the 
        // second linked list 
        temp1 = l2; 
    } 
} 
  
// Driver Code 
public static void main(String args[]) 
{ 
    Node l1 = null, l2 = null; 
  
    // Creating 1st list 
    // 2 . 5 
    l1 = push(l1, 5); 
    l1 = push(l1, 2); 
  
    // Creating 2nd list 
    // 4 . 5 . 6 . 7 . 8 
    l2 = push(l2, 8); 
    l2 = push(l2, 7); 
    l2 = push(l2, 6); 
    l2 = push(l2, 5); 
    l2 = push(l2, 4); 
  
    printSecondList(l1, l2); 
}
} 
  
// This code is contributed by Arnab Kundu

Python3

# Python3 program to prsecond linked list
# according to data in the first linked list
  
# Linked List Node
class new_Node: 
          
    # Constructor to initialize the node object 
    def __init__(self, data): 
        self.data = data 
        self.next = None
  
''' Function to insert a node at the beginning '''
def push(head_ref, new_data):
    new_node = new_Node(new_data)
    new_node.next = head_ref
    head_ref = new_node
    return head_ref
      
# Function to print second list according
# to the positions referred by the 1st list
def printSecondList(l1,l2):
      
    temp = l1
    temp1 = l2
      
    # While first linked list is not None.
    while (temp != None):
        i = 1
          
        # While second linked list is not equal
        # to the data in the node of the
        # first linked list.
        while (i < temp.data):
            # Keep incrementing second list
            temp1 = temp1.next
            i += 1
              
        # Print node at position in second list
        # pointed by current element of first list
        print(temp1.data,end=" ")
          
        # Increment first linked list
        temp = temp.next
          
        # Set temp1 to the start of the
        # second linked list
        temp1 = l2
  
# Driver Code
l1 = None
l2 = None
  
# Creating 1st list
# 2 . 5
l1 = push(l1, 5)
l1 = push(l1, 2)
  
# Creating 2nd list
# 4 . 5 . 6 . 7 . 8
l2 = push(l2, 8)
l2 = push(l2, 7)
l2 = push(l2, 6)
l2 = push(l2, 5)
l2 = push(l2, 4)
  
printSecondList(l1, l2)
  
# This code is contributed by shubhamsingh10

C#

// C# program to print second linked list 
// according to data in the first linked list 
using System;
  
class GFG 
{ 
      
// Linked List Node 
public class Node 
{ 
    public int data; 
    public Node next; 
}; 
  
/* Function to insert a node at the beginning */
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 head_ref; 
} 
  
// Function to print the second list according 
// to the positions referred by the 1st list 
static void printSecondList(Node l1, Node l2) 
{ 
    Node temp = l1; 
    Node temp1 = l2; 
  
    // While first linked list is not null. 
    while (temp != null) 
    { 
        int i = 1; 
  
        // While second linked list is not equal 
        // to the data in the node of the 
        // first linked list. 
        while (i < temp.data) 
        { 
            // Keep incrementing second list 
            temp1 = temp1.next; 
            i++; 
        } 
  
        // Print the node at position in second list 
        // pointed by current element of first list 
        Console.Write( temp1.data + " "); 
  
        // Increment first linked list 
        temp = temp.next; 
  
        // Set temp1 to the start of the 
        // second linked list 
        temp1 = l2; 
    } 
} 
  
// Driver Code 
public static void Main() 
{ 
    Node l1 = null, l2 = null; 
  
    // Creating 1st list 
    // 2 . 5 
    l1 = push(l1, 5); 
    l1 = push(l1, 2); 
  
    // Creating 2nd list 
    // 4 . 5 . 6 . 7 . 8 
    l2 = push(l2, 8); 
    l2 = push(l2, 7); 
    l2 = push(l2, 6); 
    l2 = push(l2, 5); 
    l2 = push(l2, 4); 
  
    printSecondList(l1, l2); 
} 
} 
  
// This code has been contributed by 29AjayKumar

Javascript

<script>
  
// JavaScript program to print second linked list 
// according to data in the first linked list 
  
class Node
{
    constructor()
    {
        this.data=0;
        this.next=null;
    }
}
  
/* Function to insert a node at the beginning */
function push(head_ref, new_data) 
{
    let new_node = new Node(); 
    
    new_node.data = new_data; 
    new_node.next = (head_ref); 
    (head_ref) = new_node;
    return head_ref; 
}
  
// Function to print the second list according 
// to the positions referred by the 1st list 
function printSecondList(l1,l2)
{
    let temp = l1; 
    let temp1 = l2; 
    
    // While first linked list is not null. 
    while (temp != null)
    { 
        let i = 1; 
    
        // While second linked list is not equal 
        // to the data in the node of the 
        // first linked list. 
        while (i < temp.data) 
        { 
            // Keep incrementing second list 
            temp1 = temp1.next; 
            i++; 
        } 
    
        // Print the node at position in second list 
        // pointed by current element of first list 
        document.write( temp1.data + " "); 
    
        // Increment first linked list 
        temp = temp.next; 
    
        // Set temp1 to the start of the 
        // second linked list 
        temp1 = l2; 
    } 
}
  
// Driver Code 
let l1 = null, l2 = null; 
    
// Creating 1st list 
// 2 . 5 
l1 = push(l1, 5); 
l1 = push(l1, 2); 
  
// Creating 2nd list 
// 4 . 5 . 6 . 7 . 8 
l2 = push(l2, 8); 
l2 = push(l2, 7); 
l2 = push(l2, 6); 
l2 = push(l2, 5); 
l2 = push(l2, 4); 
  
printSecondList(l1, l2); 
  
// This code is contributed by avanitrachhadiya2155
  
</script>
Producción

5 8 

Complete Interview Preparation - GFG

Complejidad del tiempo: O(n^2)

Como estamos usando bucles anidados y recorriendo los elementos de la segunda lista para cada elemento de la primera lista.

Espacio Auxiliar: O(1)

Como espacio adicional constante se utiliza.

Otro enfoque:

Como sabemos que los datos de la primera lista están ordenados, podemos hacer uso de este hecho para recorrer la segunda lista.

  1. Haga dos punteros al encabezado de ambas listas.
  2. Poner un contador a 1
  3. Siga incrementando el contador y avanzando en la segunda lista hasta que el valor del contador sea menor que los datos en el puntero actual en la primera lista 
  4. Imprima los datos del puntero de la segunda lista e incremente el puntero a la primera lista
  5. Repita los pasos 3 y 4 hasta que el puntero a la primera lista no sea NULL.

implementación:

C++

// C++ program to print second linked list
// according to data in the first linked list
#include <iostream>
using namespace std;
  
// Linked List Node
struct Node {
    int data;
    struct Node* next;
};
  
/* Function to insert a node at the beginning */
void push(struct 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;
}
  
// Function to print the second list according
// to the positions referred by the 1st list
void printSecondList(Node* l1, Node* l2)
{
    struct Node* temp1 = l1;
    struct Node* temp2 = l2;
  
    int counter = 1;
  
    // While first linked list is not null.
    while (temp1 != NULL) {
  
        // while the counter is less than the data at temp1
        while (counter < temp1->data) {
            // Keep incrementing second list
            temp2 = temp2->next;
            counter++;
        }
  
        // Print the node at position in second list
        // pointed by current element of first list
        cout << temp2->data << " ";
  
        // Increment first linked list
        temp1 = temp1->next;
    }
}
  
// Driver Code
int main()
{
    struct Node *l1 = NULL, *l2 = NULL;
  
    // Creating 1st list
    // 2 -> 5
    push(&l1, 5);
    push(&l1, 2);
  
    // Creating 2nd list
    // 4 -> 5 -> 6 -> 7 -> 8
    push(&l2, 8);
    push(&l2, 7);
    push(&l2, 6);
    push(&l2, 5);
    push(&l2, 4);
  
    printSecondList(l1, l2);
  
    return 0;
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)

Java

// Java program to print second linked list
// according to data in the first linked list
class GFG {
  
    // Linked List Node
    static class Node {
        int data;
        Node next;
    };
  
    /* Function to insert a node at the beginning */
    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 head_ref;
    }
  
    // Function to print the second list according
    // to the positions referred by the 1st list
    static void printSecondList(Node l1, Node l2)
    {
        Node temp1 = l1;
        Node temp2 = l2;
  
        int counter = 1;
  
        // While first linked list is not null.
        while (temp1 != null) {
  
            // while the counter is less than the data at
            // temp1
            while (counter < temp1.data) {
                // Keep incrementing second list
                temp2 = temp2.next;
                counter++;
            }
  
            // Print the node at position in second list
            // pointed by current element of first list
            System.out.print(temp2.data + " ");
  
            // Increment first linked list
            temp1 = temp1.next;
        }
    }
  
    // Driver Code
    public static void main(String args[])
    {
        Node l1 = null, l2 = null;
  
        // Creating 1st list
        // 2 . 5
        l1 = push(l1, 5);
        l1 = push(l1, 2);
  
        // Creating 2nd list
        // 4 . 5 . 6 . 7 . 8
        l2 = push(l2, 8);
        l2 = push(l2, 7);
        l2 = push(l2, 6);
        l2 = push(l2, 5);
        l2 = push(l2, 4);
  
        printSecondList(l1, l2);
    }
}
  
// This code is contributed by Abhijeet Kumar(abhijeet19403)

Python3

# Python3 program to prsecond linked list
# according to data in the first linked list
  
# Linked List Node
  
  
class new_Node:
  
    # Constructor to initialize the node object
    def __init__(self, data):
        self.data = data
        self.next = None
  
  
''' Function to insert a node at the beginning '''
  
  
def push(head_ref, new_data):
    new_node = new_Node(new_data)
    new_node.next = head_ref
    head_ref = new_node
    return head_ref
  
# Function to print second list according
# to the positions referred by the 1st list
  
  
def printSecondList(l1, l2):
  
    temp1 = l1
    temp2 = l2
  
    counter = 1
    # While first linked list is not None.
    while (temp1 != None):
  
        # while the counter is less than the data at temp1
        while (counter < temp1.data):
            # Keep incrementing second list
            temp2 = temp2.next
            counter += 1
  
        # Print node at position in second list
        # pointed by current element of first list
        print(temp2.data, end=" ")
  
        # Increment first linked list
        temp1 = temp1.next
  
  
# Driver Code
l1 = None
l2 = None
  
# Creating 1st list
# 2 . 5
l1 = push(l1, 5)
l1 = push(l1, 2)
  
# Creating 2nd list
# 4 . 5 . 6 . 7 . 8
l2 = push(l2, 8)
l2 = push(l2, 7)
l2 = push(l2, 6)
l2 = push(l2, 5)
l2 = push(l2, 4)
  
printSecondList(l1, l2)
  
# This code is contributed by Abhijeet Kumar(abhijeet19403)

C#

// C# program to print second linked list
// according to data in the first linked list
using System;
  
class GFG {
  
    // Linked List Node
    public class Node {
        public int data;
        public Node next;
    };
  
    /* Function to insert a node at the beginning */
    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 head_ref;
    }
  
    // Function to print the second list according
    // to the positions referred by the 1st list
    static void printSecondList(Node l1, Node l2)
    {
        Node temp1 = l1;
        Node temp2 = l2;
  
        int counter = 1;
        // While first linked list is not null.
        while (temp1 != null) {
            // while the counter is less than the data at
            // temp1
            while (counter < temp1.data) {
                // Keep incrementing second list
                temp2 = temp2.next;
                counter++;
            }
  
            // Print the node at position in second list
            // pointed by current element of first list
            Console.Write(temp2.data + " ");
  
            // Increment first linked list
            temp1 = temp1.next;
        }
    }
  
    // Driver Code
    public static void Main()
    {
        Node l1 = null, l2 = null;
  
        // Creating 1st list
        // 2 . 5
        l1 = push(l1, 5);
        l1 = push(l1, 2);
  
        // Creating 2nd list
        // 4 . 5 . 6 . 7 . 8
        l2 = push(l2, 8);
        l2 = push(l2, 7);
        l2 = push(l2, 6);
        l2 = push(l2, 5);
        l2 = push(l2, 4);
  
        printSecondList(l1, l2);
    }
}
  
// This code has been contributed by Abhijeet Kumar(abhijeet19403)

Javascript

<script>
  
// JavaScript program to print second linked list 
// according to data in the first linked list 
  
class Node
{
    constructor()
    {
        this.data=0;
        this.next=null;
    }
}
  
/* Function to insert a node at the beginning */
function push(head_ref, new_data) 
{
    let new_node = new Node(); 
    
    new_node.data = new_data; 
    new_node.next = (head_ref); 
    (head_ref) = new_node;
    return head_ref; 
}
  
// Function to print the second list according 
// to the positions referred by the 1st list 
function printSecondList(l1,l2)
{
    let temp1 = l1; 
    let temp2 = l2; 
    
      let counter = 1;
    // While first linked list is not null. 
    while (temp1 != null)
    { 
  
        // while the counter is less than the data at temp1 
        while (counter < temp1.data) 
        { 
            // Keep incrementing second list 
            temp2 = temp2.next; 
            counter++; 
        } 
    
        // Print the node at position in second list 
        // pointed by current element of first list 
        document.write( temp2.data + " "); 
    
        // Increment first linked list 
        temp1 = temp1.next; 
    } 
}
  
// Driver Code 
let l1 = null, l2 = null; 
    
// Creating 1st list 
// 2 . 5 
l1 = push(l1, 5); 
l1 = push(l1, 2); 
  
// Creating 2nd list 
// 4 . 5 . 6 . 7 . 8 
l2 = push(l2, 8); 
l2 = push(l2, 7); 
l2 = push(l2, 6); 
l2 = push(l2, 5); 
l2 = push(l2, 4); 
  
printSecondList(l1, l2); 
  
// This code is contributed by Abhijeet Kumar(abhijeet19403)
  
</script>
Producción

5 8 

Complejidad de tiempo: O(n)

Aunque estamos usando bucles anidados, el número total de operaciones está limitado solo a O (n).

Espacio Auxiliar: O(1)

Como espacio adicional constante se utiliza.

Este enfoque fue aportado por Abhijeet Kumar.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por PRIYAJITDAS 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 *