Print Nodes Of Linked List At Given indexes

This article will discuss how to print nodes of linked list at given indexes. Printing nodes of linked lists is a must to know task if you are practicing linked list. Having knowledge on data structures will definitely help for clearing the interview in the tech companies. Now let’s move to our topic of how to print nodes of linked list at given indexes.

Problem Statement

Given two singly linked lists l1 and l2. l2 is a singly linked list containing various indices in sorted order. We need to print the data in l1 at indices mentioned in l2. (indices are 1 based).

Input
l1:

l2:

Output
5 10 1

Problem Statement Understanding How to Print Nodes of Linked List At The Given Indexes

Let’s understand this problem with the above example. We have 5 -> 18 -> 9 -> 10 -> 1 -> 73 -> 11 as l1 the given linked list and 1 -> 4 -> 5 as l2 the linked list containing the indices to print.

Lets mark the indices of the nodes of a given linked list l1.

Now let’s look at the required list of indices and find the corresponding nodes.
The given list of indices l2 is: 1 -> 4 -> 5
Node at index 1 = 5
Node at index 4 = 10
Node at index 5 = 1

So we print 5 10 1 as the output.

Approach To Print Nodes of Linked List At The Given Indexes

I hope you got a basic idea of what we need to do to solve this problem. The idea is simple, since the linked list containing indices (l2) is sorted, we just need to iterate through the linked list containing values (l1) while keeping track of the current index and the index to print. Whenever the current index and index to print match, we print the value at that index and update the index to print with the next node in the linked list l2, and move to the next node in l2.

Since it is clear what we need to do, take some time and think about how we are going to do it.

Algorithm To Print Nodes of Linked List At The Given Indexes

  • Declare 2 variables curr_indx and indx_to_print and initialize them as curr_indx = 1 and indx_to_print = l2->val i.e. the first index to print.
  • Now iterate through the linked list l1 till we reach the end of either of the linked list.
  • In each iteration compare the value of curr_indx with indx_to_print. If they match
  • Print the value of the current node in l1.
  • Move to the next node in l2
  • If there are more nodes in l2 (i.e. l2!=NULL), then update the value in indx_to_print with the value in l2.
  • Increment the curr_indx by 1.

Dry Run To Print Nodes of Linked List At The Given Indexes

Implementation


#include<stdio.h>
#include<stdlib.h>

struct Node {
    int data;
    struct Node* next;
};
 
/* Function to insert a node at the beginning */
void push(struct Node** head_ref, int new_data)
{
    struct Node *new_node = (struct Node *) malloc(sizeof(struct 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(struct Node* l1,struct 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
        printf("%d ",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;
}

#include
using namespace std;

struct Node {
    int val;
    Node* next;

    Node(int value){
        val = value;
        next = NULL;
    }
};

void push_front(Node** head, int new_val){
    Node* new_node = new Node(new_val);
    new_node->next = *head;
    *head = new_node;
}

void printAtIndices(Node* l1, Node* l2){
    int curr_index = 1;
    int indx_to_print = l2->val;

    while(l1!=NULL && l2!=NULL){
        if(curr_index == indx_to_print){
            cout<val<<" ";
            l2 = l2->next;
            
            if(l2!=NULL) indx_to_print = l2->val;
        }
        l1 = l1->next;
        curr_index ++;
    }
}

int main(){
    Node* l1 = NULL;
    push_front(&l1, 11);
    push_front(&l1, 73);
    push_front(&l1, 1);
    push_front(&l1, 10);
    push_front(&l1, 9);
    push_front(&l1, 18);
    push_front(&l1, 5);
    // 5 18 9 10 1 73 11
    
    Node* l2 = NULL;
    push_front(&l2, 5);
    push_front(&l2, 4);
    push_front(&l2, 1);
    // 1 4 5

    printAtIndices(l1,l2);
    // 5 10 1
    return 0;
}

class Indexes
{
    static class Node
    {
	    int data;
	    Node next;
    };
    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;

	    l1 = push(l1, 5);
	    l1 = push(l1, 2);

	    l2 = push(l2, 8);
	    l2 = push(l2, 7);
	    l2 = push(l2, 6);
	    l2 = push(l2, 5);
	    l2 = push(l2, 4);

	    printSecondList(l1, l2);
    }
}

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

def push(head_ref, new_data):
	new_node = new_Node(new_data)
	new_node.next = head_ref
	head_ref = new_node
	return head_ref
	
def printSecondList(l1,l2):
	
	curr_index = 1
	index_to_print = l2.data

	while l1 and l2:
		if curr_index == index_to_print:
			print(l1.data, end=" ")
			l2 = l2.next

			if l2:
				index_to_print = l2.data
		l1 = l1.next
		curr_index +=1

l1 = None
l2 = None

l1 = push(l1, 11)
l1 = push(l1, 73)
l1 = push(l1, 1)
l1 = push(l1, 10)
l1 = push(l1, 9)
l1 = push(l1, 18)
l1 = push(l1, 5)

l2 = push(l2, 5)
l2 = push(l2, 4)
l2 = push(l2, 1)

printSecondList(l1, l2)

Output

5 10 1

Time complexity To Print Nodes of Linked List At The Given Indexes: O(n), where n is the length of the linked list.
Space complexity To Print Nodes of Linked List At The Given Indexes: O(1), as we aren’t using any extra space.

Through this article, we learned how to print nodes of a linked list at the given indices. Problems like these are good for strengthening your concepts in LinkedList. Having skills like Data Structures always help in clearning the Technical Interviews for the Giant Firms. I would highly recommend you to practice more such problems from Linked List.

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Singly linked list vs doubly linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Bubble sort linked list
Deletion in doubly linked list Delete the middle node of a linked list
Polynomial addition using linked list Find max value and min value in linked list
Insert a node at a specific position in a linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Delete a node from linked list at a given position
Remove duplicates from unsorted linked list Reverse a linked list in Python

FAQ Related to Print Nodes Of Linked List At Given Indexes

  1. What’s the head of a linked list?

  2. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference. A linked list is a dynamic data structure.

  3. What are nodes in the linked list?

  4. A node is a collection of two sub-elements or parts. A data part that stores the element and a next part that stores the link to the next node. A linked list is formed when many such nodes are linked together to form a chain. Each node points to the next node present in the order.

  5. What is the pointer in the linked list?

  6. The pointer variable that points to the first node which is named head.

Leave a Reply

Your email address will not be published. Required fields are marked *