Print sublist of a given Linked List specified by given indices

0 0 6 minutes read

Given a Linkedlist and two indices A and B, the task is to print a sublist starting from A and ending at B.

Examples:

Input: list = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> NULL, A = 3, B = 9
Output: 3 4 5 6 7 8 9

Input: list = 1 -> 3 -> 4 -> 10 -> NULL, A = 2, B = 2
Output: 3

Approach:
Follow the steps below to solve the problem:

Create three instance variables:
1. current: Head of the given linked list
2. subcurrent: Head of the sublist
3. subend:Tail of the sublist.
Traverse the linked list and initialize an index_count variable which increments after each iteration.
Set subcurrent as the node being currently pointed when the value of the index_count is equal to A.
If index_count is equal to B, assign subend to the current node being referenced. Point subend.next to NULL to denote the end of the sublist.
Print the list contents from subcurrent to subend.

Below code is the implementation of the above approach:

C++

// C++ Program to find the 
// subList in a linked list
#include<bits/stdc++.h>
using namespace std;
 
// structure of linked list
struct Node{
    int data;
    Node* next;
    Node(int data){
        this->data = data;
        this->next = NULL;
    }
};
 
// function to push a node at beginning of a linked list
Node* pushNode(Node* head, int new_data){
    Node* new_node = new Node(new_data);
    new_node->next = head;
    head = new_node;
    return head;
}
 
// function to find sublist
Node* subList(Node* head, int A, int B){
    Node* subcurrent = NULL;
    Node* subend = NULL;
    Node* current = head;
    int i = 1;
     
    // traverse between indices
    while(current != NULL && i <= B){
        // if the starting index
        // of the sublist is found
        if(i == A){
            subcurrent = current;
        }
         
        // if the ending index of the
        // sublist is found
        if(i == B){
            subend = current;
            subend->next = NULL;
        }
         
        // move to next node
        current = current->next;
        i++;
    }
     
    // return the head of the sublist
    return subcurrent;
}
 
// function to print the linked list
void traversing(Node* head){
    Node* current = head;
    while(current != NULL){
        cout<<current->data<<" -> ";
        current = current->next;
    }
}
 
// Driver code
int main(){
    Node* head = NULL;
     
    int N = 1;
    int value = 10;
     
    while(N < 11){
        head = pushNode(head, value--);
        N++;
    }
     
    // starting index
    int A = 3;
     
    // ending index
    int B = 9;
     
    head = subList(head, A, B);
    traversing(head);
    return 0;
}
// this code is contributed by Kirti Agarwal

Java

// Java Program to find the
// subList in a linked list
 
import java.util.Scanner;
 
// Class representing the
// structure of a Linked List
public class LinkedListSublist {
    Node head;
    class Node {
        int data;
        Node next = null;
        Node(int new_data)
        {
            data = new_data;
        }
    }
 
    // Function to push node
    // at beginning of a
    // Linked List
    public void pushNode(int new_data)
    {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
 
    // Function to find sublist
    public Node subList(Node head,
                        int A,
                        int B)
    {
        Node subcurrent = null;
        Node subend = null;
        Node current = head;
        int i = 1;
 
        // traverse between indices
        while (current != null
               && i <= B) {
 
            // If the starting index
            // of the sublist is found
            if (i == A) {
                subcurrent = current;
            }
 
            // If the ending index of
            // the sublist is found
            if (i == B) {
                subend = current;
                subend.next = null;
            }
 
            // Move to next node
            current = current.next;
            i++;
        }
 
        // Return the head
        // of the sublist
        return subcurrent;
    }
 
    // Function to print
    // the linked list
    public void traversing()
    {
        Node current = head;
        while (current != null) {
            System.out.print(current.data
                             + " -> ");
            current = current.next;
        }
    }
 
    // Driver Program
    public static void main(String args[])
    {
 
        LinkedListSublist list
            = new LinkedListSublist();
        int N = 1;
        int value = 10;
 
        while (N < 11) {
            list.pushNode(value--);
            N++;
        }
 
        // Starting index
        int A = 3;
 
        // Ending index
        int B = 9;
 
        list.head
            = list.subList(
                list.head, A, B);
        list.traversing();
    }
}

Python3

# Python3 program to find the
# subList in a linked list
class Node:
     
    def __init__(self, data):
         
        self.data = data
        self.next = None
  
# Class representing the
# structure of a Linked List
class LinkedListSublist:
     
    def __init__(self):
         
        self.head = None
     
    # Function to push node
    # at beginning of a
    # Linked List
    def pushNode(self, new_data):
         
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
     
    # Function to find sublist
    def subList(self, head, A, B):
         
        subcurrent = None
        subend = None
        current = self.head
        i = 1
  
        # Traverse between indices
        while (current != None and i <= B):
  
            # If the starting index
            # of the sublist is found
            if (i == A):
                subcurrent = current
  
            # If the ending index of
            # the sublist is found
            if (i == B):
                subend = current
                subend.next = None
  
            # Move to next node
            current = current.next
            i += 1
  
        # Return the head
        # of the sublist
        return subcurrent
         
    # Function to print
    # the linked list
    def traversing(self):
     
        current = self.head
         
        while (current != None):
            print(current.data, end = " -> ")
            current = current.next
  
# Driver Code
if __name__=='__main__':
     
    list = LinkedListSublist()
  
    N = 1
    value = 10
 
    while (N < 11):
        list.pushNode(value)
        value -= 1
        N += 1
 
    # Starting index
    A = 3
 
    # Ending index
    B = 9
 
    list.head = list.subList(list.head, A, B)
    list.traversing()
     
# This code is contributed by pratham76

C#

// C# Program to find the
// subList in a linked list
using System;
 
// Class representing the
// structure of a Linked List
public class LinkedListSublist 
{
     
    public Node head;
    public class Node 
    {
        public int data;
        public Node next = null;
        public Node(int new_data)
        {
            data = new_data;
        }
    }
  
    // Function to push node
    // at beginning of a
    // Linked List
    public void pushNode(int new_data)
    {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
  
    // Function to find sublist
    public Node subList(Node head,
                        int A,
                        int B)
    {
        Node subcurrent = null;
        Node subend = null;
        Node current = head;
        int i = 1;
  
        // traverse between indices
        while (current != null
               && i <= B) 
        {
  
            // If the starting index
            // of the sublist is found
            if (i == A) 
            {
                subcurrent = current;
            }
  
            // If the ending index of
            // the sublist is found
            if (i == B) 
            {
                subend = current;
                subend.next = null;
            }
  
            // Move to next node
            current = current.next;
            i++;
        }
  
        // Return the head
        // of the sublist
        return subcurrent;
    }
  
    // Function to print
    // the linked list
    public void traversing()
    {
        Node current = head;
        while (current != null)
        {
            Console.Write(current.data
                             + " -> ");
            current = current.next;
        }
    }
  
    // Driver Program
    public static void Main(string []args)
    {
  
        LinkedListSublist list
            = new LinkedListSublist();
        int N = 1;
        int value = 10;
  
        while (N < 11)
        {
            list.pushNode(value--);
            N++;
        }
  
        // Starting index
        int A = 3;
  
        // Ending index
        int B = 9;
  
        list.head
            = list.subList(
                list.head, A, B);
        list.traversing();
    }
}
 
// This code is contributed by rutvik_56

Javascript

// JavaScript program to find the
// sublist in a linked list
// structure of linked list
class Node{
    constructor(data){
        this.data = data;
        this.next = null;
    }
}
 
// function to push a node at beginning of a linked list
function pushNode(head, new_data){
    let new_node = new Node(new_data);
    new_node.next = head;
    head = new_node;
    return head;
}
 
// function to find sublist
function subList(head, A, B){
    let subcurrent = null;
    let subend = null;
    let current = head;
    let i = 1;
     
    // traverse between indices
    while(current != null && i <= B){
        // if the starting index
        // of the sublist is found
        if(i == A){
            subcurrent = current;
        }
         
        // if the ending index of the
        // sublist is found
        if(i == B){
            subend = current;
            subend.next = null;
        }
          
        // move to next node
        current = current.next;
        i++;
    }
    // return the head of the sublist
    return subcurrent;
}
 
// function to print the linked list
function traversing(head){
    let current = head;
    while(current != null){
        console.log(current.data + "->");
        current = current.next;
    }
}
 
// driver code to test above functions
let head = null;
let N = 1;
let value = 10;
while(N < 11){
    head = pushNode(head, value--);
    N++;
}
 
// starting index
let A = 3;
 
// ending index
let B = 9;
 
head = subList(head, A, B);
traversing(head);
 
// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002)

Output:

3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 ->

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!