Print sublist of a given Linked List specified by given indices
Last Updated :
14 Feb, 2023
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:
- 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++
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int data){
this->data = data;
this->next = NULL;
}
};
Node* pushNode(Node* head, int new_data){
Node* new_node = new Node(new_data);
new_node->next = head;
head = new_node;
return head;
}
Node* subList(Node* head, int A, int B){
Node* subcurrent = NULL;
Node* subend = NULL;
Node* current = head;
int i = 1;
while(current != NULL && i <= B){
if(i == A){
subcurrent = current;
}
if(i == B){
subend = current;
subend->next = NULL;
}
current = current->next;
i++;
}
return subcurrent;
}
void traversing(Node* head){
Node* current = head;
while(current != NULL){
cout<<current->data<<" -> ";
current = current->next;
}
}
int main(){
Node* head = NULL;
int N = 1;
int value = 10;
while(N < 11){
head = pushNode(head, value--);
N++;
}
int A = 3;
int B = 9;
head = subList(head, A, B);
traversing(head);
return 0;
}
|
Java
import java.util.Scanner;
public class LinkedListSublist {
Node head;
class Node {
int data;
Node next = null;
Node(int new_data)
{
data = new_data;
}
}
public void pushNode(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
public Node subList(Node head,
int A,
int B)
{
Node subcurrent = null;
Node subend = null;
Node current = head;
int i = 1;
while (current != null
&& i <= B) {
if (i == A) {
subcurrent = current;
}
if (i == B) {
subend = current;
subend.next = null;
}
current = current.next;
i++;
}
return subcurrent;
}
public void traversing()
{
Node current = head;
while (current != null) {
System.out.print(current.data
+ " -> ");
current = current.next;
}
}
public static void main(String args[])
{
LinkedListSublist list
= new LinkedListSublist();
int N = 1;
int value = 10;
while (N < 11) {
list.pushNode(value--);
N++;
}
int A = 3;
int B = 9;
list.head
= list.subList(
list.head, A, B);
list.traversing();
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedListSublist:
def __init__(self):
self.head = None
def pushNode(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def subList(self, head, A, B):
subcurrent = None
subend = None
current = self.head
i = 1
while (current != None and i <= B):
if (i == A):
subcurrent = current
if (i == B):
subend = current
subend.next = None
current = current.next
i += 1
return subcurrent
def traversing(self):
current = self.head
while (current != None):
print(current.data, end = " -> ")
current = current.next
if __name__=='__main__':
list = LinkedListSublist()
N = 1
value = 10
while (N < 11):
list.pushNode(value)
value -= 1
N += 1
A = 3
B = 9
list.head = list.subList(list.head, A, B)
list.traversing()
|
C#
using System;
public class LinkedListSublist
{
public Node head;
public class Node
{
public int data;
public Node next = null;
public Node(int new_data)
{
data = new_data;
}
}
public void pushNode(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
public Node subList(Node head,
int A,
int B)
{
Node subcurrent = null;
Node subend = null;
Node current = head;
int i = 1;
while (current != null
&& i <= B)
{
if (i == A)
{
subcurrent = current;
}
if (i == B)
{
subend = current;
subend.next = null;
}
current = current.next;
i++;
}
return subcurrent;
}
public void traversing()
{
Node current = head;
while (current != null)
{
Console.Write(current.data
+ " -> ");
current = current.next;
}
}
public static void Main(string []args)
{
LinkedListSublist list
= new LinkedListSublist();
int N = 1;
int value = 10;
while (N < 11)
{
list.pushNode(value--);
N++;
}
int A = 3;
int B = 9;
list.head
= list.subList(
list.head, A, B);
list.traversing();
}
}
|
Javascript
class Node{
constructor(data){
this.data = data;
this.next = null;
}
}
function pushNode(head, new_data){
let new_node = new Node(new_data);
new_node.next = head;
head = new_node;
return head;
}
function subList(head, A, B){
let subcurrent = null;
let subend = null;
let current = head;
let i = 1;
while(current != null && i <= B){
if(i == A){
subcurrent = current;
}
if(i == B){
subend = current;
subend.next = null;
}
current = current.next;
i++;
}
return subcurrent;
}
function traversing(head){
let current = head;
while(current != null){
console.log(current.data + "->");
current = current.next;
}
}
let head = null;
let N = 1;
let value = 10;
while(N < 11){
head = pushNode(head, value--);
N++;
}
let A = 3;
let B = 9;
head = subList(head, A, B);
traversing(head);
|
Output:
3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 ->
Time Complexity: O(N)
Auxiliary Space: O(1)