List Reduction

CONCEPTS USED:

Linked list

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

Given a linked list of N nodes 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 -> cgdghg

SOLVING APPROACH:

  1. The idea is to create another list temp to store the reduced version of the original list.

  2. Traverse the original list and perform the following operations :-

    1. If the temp list is empty, simply append the current element into the list.
    2. If the temp list is not empty, check if the last element inserted is equal to the current element, If Yes remove the last element added.
    3. 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 temp list.

ILLUSTRATION:

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 cgdghg

SOLUTIONS:

#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: O(N), for creating an Additional linked list.

[forminator_quiz id="2135"]

This article tried to discuss Linked list. Hope this blog helps you understand and solve the problem. To practice more problems on Linked list you can check out MYCODE | Competitive Programming.

Leave a Reply

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