Open In App

Print nodes of linked list at given indexes

Last Updated : 26 Aug, 2024
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

Given head of two singly linked lists, first one is sorted and the other one is unsorted. The task is to print the elements of the second linked list according to the position pointed out by the data in the first linked list. For example, if the first linked list is 1->2->5, then you have to print the second linked list’s 1st, 2nd and 5th node’s data.

Note: All the position (represented by each node of sorted linked list) will be exist in the unsorted linked list.

Examples: 

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

Input: head1 = 2->5, head2 = 7->5->3->2->8
Output: 5->8

Table of Content

[Naive Approach]: Using Nested Loops – O(n2) Time and O(1) Space:

The idea is to use two nested loops to traverse two linked lists. The outer loop traverses the first list, while the inner loop traverses the second list until a specific position is reached, printing the data at that position.

Step-by-step approach:

  • Initialize two pointers, current1 (for the first list) and current2 (for the second list).
  • Loop through current1 until it is nullptr.
    • For each node in the first list, use a nested loop to traverse the second list until reaching the position indicated by current1->data.
    • Print the data of the node at the current position in the second list.
    • Reset current2 to the head of the second list after each outer loop iteration.

Below is the implementation of the above approach:  

C++ 
// C++ program to print second linked list
// according to data in the first linked list
#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int x) {
        data = x;
          next = nullptr;
    }
};

// Function to print the second list according
// to the positions referred by the 1st list
void printSecondList(Node* head1, Node* head2) {
    Node* current1 = head1;
    Node* current2 = head2;

    // While first linked list is not null
    while (current1 != nullptr) {
        int i = 1;

        // While second linked list is not equal
        // to the data in the node of the first linked list
        while (i < current1->data) {
            // Keep incrementing second list
            current2 = current2->next;
            i++;
        }

        // Print the node at position in second list
        // pointed by current element of first list
        cout << current2->data << " ";

        // Increment first linked list
        current1 = current1->next;

        // Set temp1 to the start of the second linked list
        current2 = head2;
    }
}

int main() {
    // create 1st list: 2 -> 5
    Node* head1 = new Node(2);
    head1->next = new Node(5);

    // create 2nd list: 4 -> 5 -> 6 -> 7 -> 8
    Node* head2 = new Node(4);
    head2->next = new Node(5);
    head2->next->next = new Node(6);
    head2->next->next->next = new Node(7);
    head2->next->next->next->next = new Node(8);

    printSecondList(head1, head2);

    return 0;
}
C 
// C program to print second linked list
// according to data in the first linked list

#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

// Function to print the second list according
// to the positions referred by the 1st list
void printSecondList(struct Node* head1, struct Node* head2) {
    struct Node* current1 = head1;
    struct Node* current2 = head2;

    // While first linked list is not null
    while (current1 != NULL) {
        int i = 1;

        // While second linked list is not equal
        // to the data in the node of the first linked list
        while (i < current1->data) {
            // Keep incrementing second list
            current2 = current2->next;
            i++;
        }

        // Print the node at position in second list
        // pointed by current element of first list
        printf("%d ", current2->data);

        // Increment first linked list
        current1 = current1->next;

        // Set temp1 to the start of the second linked list
        current2 = head2;
    }
}

struct Node *createNode(int data)
{
    struct Node *newNode = 
      (struct Node *)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

int main() {
    // create 1st list: 2 -> 5
    struct Node* head1 = createNode(2);
    head1->next = createNode(5);

    // create 2nd list
    // 4 -> 5 -> 6 -> 7 -> 8
    struct Node* head2 = createNode(4);
    head2->next = createNode(5);
    head2->next->next = createNode(6);
    head2->next->next->next = createNode(7);
    head2->next->next->next->next = createNode(8);

    printSecondList(head1, head2);

    return 0;
}
Java 
// Java program to print second linked list 
// according to data in the first linked list 
class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class GfG {

    // Function to print the second list according
    // to the positions referred by the 1st list
    static void printSecondList(Node head1, Node head2) {
        Node current1 = head1;
        Node current2 = head2;

        // While first linked list is not null
        while (current1 != null) {
            int i = 1;

            // While second linked list is not equal
            // to the data in the node of the first linked list
            while (i < current1.data) {
                // Keep incrementing second list
                current2 = current2.next;
                i++;
            }

            // Print the node at position in second list
            // pointed by current element of first list
            System.out.print(current2.data + " ");

            // Increment first linked list
            current1 = current1.next;

            // Set temp1 to the start of the second linked list
            current2 = head2;
        }
    }

    public static void main(String[] args) {
        // create 1st list: 2 -> 5
        Node head1 = new Node(2);
        head1.next = new Node(5);

        // create 2nd list
        // 4 -> 5 -> 6 -> 7 -> 8
        Node head2 = new Node(4);
        head2.next = new Node(5);
        head2.next.next = new Node(6);
        head2.next.next.next = new Node(7);
        head2.next.next.next.next = new Node(8);

        printSecondList(head1, head2);
    }
}
Python 
# Python3 program to prsecond linked list
# according to data in the first linked list

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Function to print the second list according
# to the positions referred by the 1st list
def print_second_list(head1, head2):
    current1 = head1
    current2 = head2

    # While first linked list is not null
    while current1 is not None:
        i = 1

        # While second linked list is not equal
        # to the data in the node of the first linked list
        while i < current1.data:
            # Keep incrementing second list
            current2 = current2.next
            i += 1

        # Print the node at position in second list
        # pointed by current element of first list
        print(current2.data, end=" ")

        # Increment first linked list
        current1 = current1.next

        # Set temp1 to the start of the second linked list
        current2 = head2

# create 1st list: 2 -> 5
head1 = Node(2)
head1.next = Node(5)

# create 2nd list: 4 -> 5 -> 6 -> 7 -> 8
head2 = Node(4)
head2.next = Node(5)
head2.next.next = Node(6)
head2.next.next.next = Node(7)
head2.next.next.next.next = Node(8)

print_second_list(head1, head2)
C# 
// C# program to print second linked list 
// according to data in the first linked list 

using System;

class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class GfG {

    // Function to print the second list according
    // to the positions referred by the 1st list
    public static void PrintSecondList(Node head1, Node head2) {
        Node current1 = head1;
        Node current2 = head2;

        // While first linked list is not null
        while (current1 != null) {
            int i = 1;

            // While second linked list is not equal
            // to the data in the node of the first linked list
            while (i < current1.data) {
                // Keep incrementing second list
                current2 = current2.next;
                i++;
            }

            // Print the node at position in second list
            // pointed by current element of first list
            Console.Write(current2.data + " ");

            // Increment first linked list
            current1 = current1.next;

            // Set temp1 to the start of the second linked list
            current2 = head2;
        }
    }

    public static void Main(string[] args) {
        // create 1st list: 2 -> 5
        Node head1 = new Node(2);
        head1.next = new Node(5);

        // create 2nd list: 4 -> 5 -> 6 -> 7 -> 8
        Node head2 = new Node(4);
        head2.next = new Node(5);
        head2.next.next = new Node(6);
        head2.next.next.next = new Node(7);
        head2.next.next.next.next = new Node(8);

        PrintSecondList(head1, head2);
    }
}
JavaScript 
// JavaScript program to print second linked list 
// according to data in the first linked list 

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

// Function to print the second list according
// to the positions referred by the 1st list
function printSecondList(head1, head2) {
    let current1 = head1;
    let current2 = head2;

    // While first linked list is not null
    while (current1 !== null) {
        let i = 1;

        // While second linked list is not equal
        // to the data in the node of the first linked list
        while (i < current1.data) {
            // Keep incrementing second list
            current2 = current2.next;
            i++;
        }

        // Print the node at position in second list
        // pointed by current element of first list
        console.log(current2.data);

        // Increment first linked list
        current1 = current1.next;

        // Set temp1 to the start of the second linked list
        current2 = head2;
    }
}

// create 1st list: 2 -> 5
let head1 = new Node(2);
head1.next = new Node(5);

// create 2nd list: 4 -> 5 -> 6 -> 7 -> 8
let head2 = new Node(4);
head2.next = new Node(5);
head2.next.next = new Node(6);
head2.next.next.next = new Node(7);
head2.next.next.next.next = new Node(8);

printSecondList(head1, head2);

Output
5 8

Time Complexity: O(n), To traverse the second linked list completely.
Auxiliary Space: O(1)

[Expected Approach]: Single-Pass List Traversal – O(m+n) Time and O(1) Space

The idea is to utilize the sorted order of the first list to traverse the second list more efficiently, reducing unnecessary comparisons by skipping irrelevant nodes.

Step-by-step approach:

  • Initialize two pointers: current1 for the first list and current2 for the second list.
  • For each node in the first list, retrieve its data as targetPos.
  • Traverse the second list to the position indicated by targetPos.
  • Print the data at that position if it exists.

Below is the implementation of the above approach: 

C++ 
// C++ program to print second linked list
// according to data in the first linked list
#include <bits/stdc++.h>
using namespace std;

class Node{
  public:
    int data;
    Node *next;
    Node(int x){
        data = x;
        next = nullptr;
    }
};

// Function to print the second list according
// to the positions referred by the 1st list
void printSecondList(Node *head1, Node *head2){

    // Step 1: Traverse the second list with a pointer
    Node *current2 = head2;
   // Position index starts at 1

    int currentPos = 1;
  
    // Traverse the first linked list to get positions
    Node *current1 = head1;
    while (current1 != nullptr)
    {
        int targetPos = current1->data;

        // Move the pointer in the second list to the target position
        while (current2 != nullptr && currentPos < targetPos)
        {
            current2 = current2->next;
            currentPos++;
        }

        // Print the node data if it matches the target position
        if (current2 != nullptr && currentPos == targetPos)
            cout << current2->data << " ";

        // Move to the next node in the first list
        current1 = current1->next;
    }
    cout << endl;
}

int main()
{
    // create 1st list: 2 -> 5
    Node *head1 = new Node(2);
    head1->next = new Node(5);

    // create 2nd list: 4 -> 5 -> 6 -> 7 -> 8
    Node *head2 = new Node(4);
    head2->next = new Node(5);
    head2->next->next = new Node(6);
    head2->next->next->next = new Node(7);
    head2->next->next->next->next = new Node(8);

    printSecondList(head1, head2);

    return 0;
}
C 
// C program to print second linked list
// according to data in the first linked list
#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int data;        
    struct Node *next; 
};

// Function to print elements of the second list based on positions
//  from the first list
void printSecondList(struct Node *head1, struct Node *head2)
{

    // Pointer to traverse the second list
    struct Node *current2 = head2;

    // Start position index at 1
    int currentPos = 1;

    // Pointer to traverse the first list
    struct Node *current1 = head1;
    while (current1 != NULL)
    {

        // Get the target position from the first list
        int targetPos = current1->data;

        // Move the pointer in the second list to the target position
        while (current2 != NULL && currentPos < targetPos)
        {
            current2 = current2->next;
            currentPos++;
        }

        // Print the node data if it matches the target position
        if (current2 != NULL && currentPos == targetPos)
          printf("%d ", current2->data);

        // Move to the next node in the first list
        current1 = current1->next;
    }
    printf("\n");
}

struct Node *createNode(int data)
{
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

int main()
{
    // Create 1st list: 2 -> 5
    struct Node *head1 = createNode(2);
    head1->next = createNode(5);

    // Create 2nd list: 4 -> 5 -> 6 -> 7 -> 8
    struct Node *head2 = createNode(4);
    head2->next = createNode(5);
    head2->next->next = createNode(6);
    head2->next->next->next = createNode(7);
    head2->next->next->next->next = createNode(8);

    printSecondList(head1, head2);

    return 0;
}
Java 
// Java program to print second linked list
// according to data in the first linked list
class Node {
    int data;
    Node next;
    Node(int x){
        data = x;
        next = null;
    }
}

class GfG {
    // Function to print elements of the second list based
    // on positions from the first list
    static void printSecondList(Node head1, Node head2)
    {
        // Pointer to traverse the second list
        Node current2 = head2;

        // Start position index at 1
        int currentPos = 1;

        // Pointer to traverse the first list
        Node current1 = head1;
        while (current1 != null) {

            // Get the target position from the first list
            int targetPos = current1.data;

            // Move the pointer in the second list to the
            // target position
            while (current2 != null
                   && currentPos < targetPos) {
                current2 = current2.next;
                currentPos++;
            }

            // Print the node data if it matches the target
            // position
            if (current2 != null
                && currentPos == targetPos) {
                System.out.print(current2.data + " ");
            }

            // Move to the next node in the first list
            current1 = current1.next;
        }
        System.out.println();
    }

    public static void main(String[] args)
    {
        // Create 1st list: 2 -> 5
        Node head1 = new Node(2);
        head1.next = new Node(5);

        // Create 2nd list: 4 -> 5 -> 6 -> 7 -> 8
        Node head2 = new Node(4);
        head2.next = new Node(5);
        head2.next.next = new Node(6);
        head2.next.next.next = new Node(7);
        head2.next.next.next.next = new Node(8);

        printSecondList(head1, head2);
    }
}
Python 
# Python program to print second linked list
# according to data in the first linked list
class Node:
    def __init__(self, x):
        self.data = x
        self.next = None

def print_second_list(head1, head2):
  
   # Pointer to traverse the second list
    current2 = head2 
    
    # Start position index at 1
    current_pos = 1  
    
    # Pointer to traverse the first list
    current1 = head1  
    while current1:
      
        # Get the target position from the first list
        target_pos = current1.data  

        # Move the pointer in the second list to the target position
        while current2 and current_pos < target_pos:
            current2 = current2.next
            current_pos += 1

        # Print the node data if it matches the target position
        if current2 and current_pos == target_pos:
            print(current2.data, end=" ")

        # Move to the next node in the first list
        current1 = current1.next
    
    print()

# Create 1st list: 2 -> 5
head1 = Node(2)
head1.next = Node(5)

# Create 2nd list: 4 -> 5 -> 6 -> 7 -> 8
head2 = Node(4)
head2.next = Node(5)
head2.next.next = Node(6)
head2.next.next.next = Node(7)
head2.next.next.next.next = Node(8)

print_second_list(head1, head2)
C# 
using System;

class Node {
    public int data;
    public Node next;
    public Node(int x){
        data = x;
        next = null;
    }
}

class GfG{
    // Function to print elements of the second list based
    // on positions from the first list
    static void PrintSecondList(Node head1, Node head2)
    {
       // Pointer to traverse the second list
        Node current2 = head2; 

        // Start position index at 1
        int currentPos = 1; 
        
      // Pointer to traverse the first list
        Node current1 = head1; 
        while (current1 != null) {
            // Get the target position from the first list
            int targetPos = current1.data; 

            // Move the pointer in the second list to the
            // target position
            while (current2 != null
                   && currentPos < targetPos) {
                current2 = current2.next;
                currentPos++;
            }

            // Print the node data if it matches the target
            // position
            if (current2 != null
                && currentPos == targetPos) {
                Console.Write(current2.data + " ");
            }

            // Move to the next node in the first list
            current1 = current1.next;
        }
        Console.WriteLine();
    }

    static void Main()
    {
        // Create 1st list: 2 -> 5
        Node head1 = new Node(2);
        head1.next = new Node(5);

        // Create 2nd list: 4 -> 5 -> 6 -> 7 -> 8
        Node head2 = new Node(4);
        head2.next = new Node(5);
        head2.next.next = new Node(6);
        head2.next.next.next = new Node(7);
        head2.next.next.next.next = new Node(8);

        PrintSecondList(head1, head2);
    }
}
JavaScript 
class Node {
    constructor(x)
    {
        this.data = x;
        this.next = null;
    }
}

// Function to print elements of the second list based on
// positions from the first list
function printSecondList(head1, head2)
{
    // Pointer to traverse the second list
    let current2 = head2; 
        
    // Start position index at 1
    let currentPos = 1; 
    
    // Pointer to traverse the first list
    let current1 = head1; 
    while (current1 !== null) {
    
        // Get the target position from the first list
        let targetPos= current1.data; 

        // Move the pointer in the second list to the target
        // position
        while (current2 !== null
               && currentPos < targetPos) {
            current2 = current2.next;
            currentPos++;
        }

        // Print the node data if it matches the target
        // position
        if (current2 !== null && currentPos === targetPos) {
            process.stdout.write(current2.data + " ");
        }

        // Move to the next node in the first list
        current1 = current1.next;
    }
    console.log();
}

// Create 1st list: 2 -> 5
let head1 = new Node(2);
head1.next = new Node(5);

// Create 2nd list: 4 -> 5 -> 6 -> 7 -> 8
let head2 = new Node(4);
head2.next = new Node(5);
head2.next.next = new Node(6);
head2.next.next.next = new Node(7);
head2.next.next.next.next = new Node(8);

printSecondList(head1, head2);

Output
5 8

Time Complexity: O(m+n), At worst case we would traverse each nodes of both linked list
Auxiliary Space: O(1)




Next Article
Print the alternate nodes of linked list (Iterative Method)

P
PRIYAJITDAS
News
Improve

Similar Reads

Article Tags :
Practice Tags :
three90RightbarBannerImg
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox
  翻译：