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 9Input: 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:
- current: Head of the given linked list
- subcurrent: Head of the sublist
- 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 liststruct Node{ int data; Node* next; Node(int data){ this->data = data; this->next = NULL; }};// function to push a node at beginning of a linked listNode* 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 sublistNode* 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 listvoid traversing(Node* head){ Node* current = head; while(current != NULL){ cout<<current->data<<" -> "; current = current->next; }}// Driver codeint 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 listimport java.util.Scanner;// Class representing the// structure of a Linked Listpublic 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 listclass Node: def __init__(self, data): self.data = data self.next = None # Class representing the# structure of a Linked Listclass 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 Codeif __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 listusing System;// Class representing the// structure of a Linked Listpublic 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 listclass Node{ constructor(data){ this.data = data; this.next = null; }}// function to push a node at beginning of a linked listfunction pushNode(head, new_data){ let new_node = new Node(new_data); new_node.next = head; head = new_node; return head;}// function to find sublistfunction 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 listfunction traversing(head){ let current = head; while(current != null){ console.log(current.data + "->"); current = current.next; }}// driver code to test above functionslet head = null;let N = 1;let value = 10;while(N < 11){ head = pushNode(head, value--); N++;}// starting indexlet A = 3;// ending indexlet 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
