Last Updated on November 28, 2022 by Prepbytes
This blog Discusses the famous question “list reduction in linked list”. Linked list reduction plays an important role in improving your data structures like linked list. In linked list reduction, we have to remove the nodes. Criteria for removing nodes is the nodes with the same data and are next to each other will be removed from the linked list. Let’s discuss the reduction list in detail.
Linked List Reduction:
Given a linked list of
Nnodes such that each node have a lower case alphabet(a - z). Your task is to remove the nodes which have the same data and are next to each other.
See original problem statement here
For Example:
Input : bddbcgdghgii
Output: cgdghg
Explanation : bddbcgdghgii -> bbcgdghg -> cgdghgSOLVING APPROACH For Linked List Reduction:
-
The idea is to create another list
tempto store the reduced version of the original list. -
Traverse the original list and perform the following operations:
- If the
templist is empty, simply append the current element into the list. - If the
templist is not empty, check if the last element inserted is equal to the current element, IfYesremove the last element added. - Else if the last element is not equal to the current element, append the current element into the list. Finally our original list will be reduced and stored in the
templist.
- If the
ILLUSTRATION For Linked List Reduction:
list = bddbcgdghgii
temp is empty
Start traversing the list :-
for 1st element b, temp is empty so append into it
temp = b
for 2nd element d, b is not equal to d so append into it
temp = bd
for 3rd element d, d is equal to d so remove already added d
temp = b
for 4th element b, b is equal to b so remove already added b, temp becomes empty now
temp =
for 5th element c, temp is empty so append into it
temp = c
for 6th element g, g is not equal to c so append into it
temp = cg
for 7th element d, d is not equal to g so append into it
temp = cgd
for 8th element g, g is not equal to d so append into it
temp = cgdg
for 9th element h, h is not equal to g so append into it
temp = cgdgh
for 10th element g, g is not equal to h so append into it
temp = cgdghg
for 11th element i, i is not equal to g so append into it
temp = cgdghgi
for 12th element i, i is equal to i so remove already added i
temp = cgdghg
So, our final reduced list is cgdghgSOLUTIONS For Linked List Reduction:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
char value;
struct Node *next;
}Node;
Node* CreateNode(Node *head, char val)
{
Node *newnode = (struct Node*)malloc(sizeof(struct Node));
newnode->value = val ;
newnode->next = NULL ;
if ( head == NULL ) {
head = newnode ;
}
else
{
newnode->next=head;
head=newnode;
}
return head ;
}
void printList(Node *head) {
Node *temp = head ;
if (temp) {
while ( temp!= NULL ) {
printf ( "%c", temp->value ) ;
temp = temp->next ;
}
}
}
Node* ListDestruction(Node *Head)
{
Node *head = NULL,*t=Head;
while(t!=NULL)
{
char ch=t->value;
if(head == NULL)
head = CreateNode(head, ch);
else {
if(head->value == ch) {
Node *temp = head;
head = head->next;
free(temp);
}
else {
head = CreateNode(head,ch);
}
}
t=t->next;
}
return head;
}
int main()
{
struct Node *head = NULL ;
int size, i;
char val[100005];
scanf("%d", &size);
scanf(" %s", val);
for ( i = 0 ; i < size ; i ++ ) {
char ch=val[i];
head = CreateNode(head, ch) ;
}
head = ListDestruction(head);
if(head!=NULL)
printList(head);
else
printf("-1");
return 0;
}
#include <bits/stdc++.h>
using namespace std;
struct Node {
char data;
struct Node *next;
};
Node *insert( Node *head, char ch) {
Node *node = new Node();
if(head==NULL) {
head = new Node();
head->data = ch;
return head;
}
node->data = ch;
node->next = head;
return node;
}
void PrintList(Node *head)
{
if(head == NULL)
return;
while(head!=NULL){
cout<<head->data;
head=head->next;
}
}
Node* ListDestruction(Node *Head)
{
Node *head = NULL,*t=Head;
while(t!=NULL)
{
char ch=t->data;
if(head == NULL)
head = insert( head,ch);
else {
if(head->data == ch) {
Node *temp = head;
head = head->next;
free(temp);
}
else {
head = insert(head,ch);
}
}
t=t->next;
}
return head;
}
int main()
{
struct Node *head = NULL, *temp ;
int size, i;
string val;
cin>>size;
cin>>val;
for ( i = 0 ; i < size ; i ++ ) {
char ch=val[i];
head = insert(head, ch) ;
}
temp=ListDestruction(head);
if(temp!=NULL)
PrintList(temp);
else
cout<<-1;
return 0;
}
import java.io.*;
import java.util.*;
public class Main
{
static class SinglyLinkedListNode {
char value;
SinglyLinkedListNode next;
SinglyLinkedListNode(char nodeData) {
this.value = nodeData;
this.next = null;
}
}
static class SinglyLinkedList {
public SinglyLinkedListNode head;
public SinglyLinkedListNode tail;
public SinglyLinkedList() {
this.head = null;
this.tail = null;
}
public void insertNode( char nodeData) {
SinglyLinkedListNode node = new SinglyLinkedListNode(nodeData);
if (this.head == null) {
this.head = node;
this.tail=node;
} else {
SinglyLinkedListNode temp=this.head;
this.head=node;
this.head.next =temp;
}
}
}
static void printLinkedList( SinglyLinkedListNode head)
{
SinglyLinkedListNode temp=head;
while(temp!=null)
{
System.out.print(temp.value);
temp=temp.next;
}
}
static SinglyLinkedList ListDestruction(SinglyLinkedList list)
{
SinglyLinkedList temp = new SinglyLinkedList();
SinglyLinkedListNode current = list.head;
SinglyLinkedListNode prev = null;
while (current != null)
{
if (temp.head == null || temp.head.value != current.value) {
temp.insertNode(current.value);
} else {
temp.head = temp.head.next;
}
current = current.next;
}
return temp;
}
private static Scanner scanner = new Scanner(System.in);
public static void main( String[] args) throws IOException {
SinglyLinkedList llist = new SinglyLinkedList();
int size = scanner.nextInt();
scanner.nextLine();
String val = scanner.next();
for (int i = 0; i < size; i++) {
char ch = val.charAt(i);
llist.insertNode(ch);
}
SinglyLinkedList ans = ListDestruction(llist);
if (ans.head == null) {
System.out.println("-1");
} else {
printLinkedList(ans.head);
}
}
}
class Node: def __init__(self, data): self.data = data self.next = None def ListDestruction(Head): head = None t = Head while t: ch = t.data if head == None: head = push(head, ch) else: if head.data == ch: temp = head head = head.next del temp else: head = push(head, ch) t = t.next return head def push(head_ref, new_data): new_node = Node(new_data) new_node.data = new_data new_node.next = head_ref head_ref = new_node return head_ref def printList(node): while (node != None): print(node.data, end = " ") node = node.next if __name__=='__main__': head = None for i in "bddbcgdghgii": head = push(head, i) head = ListDestruction(head) printList(head)
Space Complexity For Linked List Reduction: O(N), for creating an Additional linked list.
This blog discusses the most efficient approach for the linked list reduction. Questions like linked list reduction always give a challenge for a programmer. Conquering linked list reduction will lead to one step moving towards your goals. To practice more problems on Linked list you can check out MYCODE | Competitive Programming.
FAQ
1. How is data removed from a linked list?
To delete a node from the linked list, we need to do the following steps:
- Find the previous node of the node to be deleted.
- Change the next of the previous node.
- Free memory for the node to be deleted.
2. What are the 3 conditions in deleting a node in a linked list?
To delete a node from the linked list, we need to do the following steps.
- Find the previous node of the node to be deleted.
- Change the next to the previous node.
- Free memory for the node to be deleted.
3. Which companies recently asked linked list reduction questions in their technical interviews?
Samsung, Josh Technologies, Squadstack and IndiaMart in their recent interviews have asked about the linked list reduction.