Remove all occurrences of one Linked list in another Linked list
Given two linked lists head1 and head2, the task is to remove all occurrences of head2 in head1 and return the head1.
Examples:
Input: head1 = 2 -> 3 -> 4 -> 5 -> 3 -> 4, head2 = 3 -> 4
Output: 2 -> 5
Explanation: After removing all occurrences of 3 -> 4 in head1 output is 2 -> 5.Input: head1 = 3 -> 6 -> 9 -> 8 -> 7, head2 = 4 -> 5 -> 2
Output: 3 -> 6 -> 9 -> 8 -> 7
Explanation: There are no occurrences of head2 in head1 so we will return head1 as it is.
Approach: This can be solved with the following idea:
We can solve this problem using a simple traversal of the linked list head1. We will keep two pointers prev and curr, where prev will keep track of the previous node of curr. For each node in head1, we will compare it with head2. If we find a match, we will remove the node by updating the next of prev to point to the next of curr. We will continue this process until we reach the end of head1.
Below are the steps involved in the implementation of codes:
- Initialize prev as NULL and curr as head1.
- Traverse the linked list head1.
- If the data of the current node is equal to the data of head2, then
- If the current node is the head node, then update head1 to point to the next node.
- Otherwise, update the next of prev to point to the next of curr.
- Else, update the prev to point to the current node.
- Update curr to point to the next node.
- Return head1.
Below is the implementation of the above approach:
C++
// C++ Implementation #include <bits/stdc++.h> using namespace std; // Linked List Node struct Node { int data; Node* next; Node( int x) { data = x; next = NULL; } }; // Function to remove all occurrences of // head2 in head1 Node* removeOccurrences(Node* head1, Node* head2) { // Initialize prev as NULL and // curr as head1 Node* prev = NULL; Node* curr = head1; // Traverse the linked list head1 while (curr != NULL) { // If the data of the current node // is equal to the data of head2 if (curr->data == head2->data && curr->next->data == head2->next->data) { // If the current node is the // head node, then update head1 // to point to the next node if (curr == head1) { head1 = curr->next->next; } // Otherwise, update the next // of prev to point to the // next of curr else { prev->next = curr->next->next; } // Update curr to point to // the next node curr = curr->next->next; } // Else, update prev to point to // the current node and curr to // point to the next node else { prev = curr; curr = curr->next; } } // Return head1 return head1; } // Function to print the linked list void printList(Node* head) { while (head != NULL) { cout << head->data; if (head->next != NULL) { cout << "->" ; } head = head->next; } cout << endl; } // Driver code int main() { // Create the linked list head1 Node* head1 = new Node(2); head1->next = new Node(3); head1->next->next = new Node(4); head1->next->next->next = new Node(5); head1->next->next->next->next = new Node(3); head1->next->next->next->next->next = new Node(4); // Create the linked list head2 Node* head2 = new Node(3); head2->next = new Node(4); // Function call head1 = removeOccurrences(head1, head2); printList(head1); return 0; } |
Java
// Java Implementation class Node { int data; Node next; public Node( int x) { data = x; next = null ; } } public class Main { // Function to remove all occurrences of head2 in head1 public static Node removeOccurrences(Node head1, Node head2) { // Initialize prev as null and curr as head1 Node prev = null ; Node curr = head1; // Traverse the linked list head1 while (curr != null ) { // If the data of the current node is equal to // the data of head2 if (curr.data == head2.data && curr.next.data == head2.next.data) { // If the current node is the head node, // then update head1 to point to the next // node if (curr == head1) { head1 = curr.next.next; } // Otherwise, update the next of prev to // point to the next of curr else { prev.next = curr.next.next; } // Update curr to point to the next node curr = curr.next.next; } // Else, update prev to point to the current // node and curr to point to the next node else { prev = curr; curr = curr.next; } } // Return head1 return head1; } // Function to print the linked list public static void printList(Node head) { while (head != null ) { System.out.print(head.data); if (head.next != null ) { System.out.print( "->" ); } head = head.next; } System.out.println(); } // Driver code public static void main(String[] args) { // Create the linked list head1 Node head1 = new Node( 2 ); head1.next = new Node( 3 ); head1.next.next = new Node( 4 ); head1.next.next.next = new Node( 5 ); head1.next.next.next.next = new Node( 3 ); head1.next.next.next.next.next = new Node( 4 ); // Create the linked list head2 Node head2 = new Node( 3 ); head2.next = new Node( 4 ); // Function call head1 = removeOccurrences(head1, head2); printList(head1); } } // This code is contributed by rambabuguphka |
Python3
# Python3 Implementation # Linked List Node class Node: def __init__( self , x): self .data = x self . next = None # Function to remove all occurrences of # head2 in head1 def removeOccurrences(head1, head2): # Initialize prev as None and # curr as head1 prev = None curr = head1 # Traverse the linked list head1 while curr: # If the data of the current node # is equal to the data of head2 if curr.data = = head2.data and curr. next .data = = head2. next .data: # If the current node is the # head node, then update head1 # to point to the next node if curr = = head1: head1 = curr. next . next # Otherwise, update the next # of prev to point to the # next of curr else : prev. next = curr. next . next # Update curr to point to # the next node curr = curr. next . next # Else, update prev to point to # the current node and curr to # point to the next node else : prev = curr curr = curr. next # Return head1 return head1 # Function to print the linked list def printList(head): while head: print (head.data, end = "") if head. next : print ( "->" , end = "") head = head. next print () # Driver code # Create the linked list head1 head1 = Node( 2 ) head1. next = Node( 3 ) head1. next . next = Node( 4 ) head1. next . next . next = Node( 5 ) head1. next . next . next . next = Node( 3 ) head1. next . next . next . next . next = Node( 4 ) # Create the linked list head2 head2 = Node( 3 ) head2. next = Node( 4 ) # Function call head1 = removeOccurrences(head1, head2) printList(head1) # This code is contributed by akshitaguprzj3 |
C#
using System; // Linked List Node public class Node { public int data; public Node next; public Node( int x) { data = x; next = null ; } } public class GFG { // Function to remove all occurrences of head2 in head1 public static Node RemoveOccurrences(Node head1, Node head2) { // Initialize prev as null and curr as head1 Node prev = null ; Node curr = head1; // Traverse the linked list head1 while (curr != null ) { // If the data of the current node is equal to the data of head2 // and the data of the next node is equal to the data of head2.next if (curr.data == head2.data && curr.next.data == head2.next.data) { // If the current node is the head node, then update head1 // to point to the next node if (curr == head1) { head1 = curr.next.next; } // Otherwise, update the next of prev to point to the next of curr else { prev.next = curr.next.next; } // Update curr to point to the next node curr = curr.next.next; } else { // Else, update prev to point to the current node and curr to point to the next node prev = curr; curr = curr.next; } } // Return head1 return head1; } // Function to print the linked list public static void PrintList(Node head) { while (head != null ) { Console.Write(head.data); if (head.next != null ) { Console.Write( "->" ); } head = head.next; } Console.WriteLine(); } // Driver code public static void Main() { // Create the linked list head1 Node head1 = new Node(2); head1.next = new Node(3); head1.next.next = new Node(4); head1.next.next.next = new Node(5); head1.next.next.next.next = new Node(3); head1.next.next.next.next.next = new Node(4); // Create the linked list head2 Node head2 = new Node(3); head2.next = new Node(4); // Function call head1 = RemoveOccurrences(head1, head2); PrintList(head1); } } |
Javascript
// Linked List Node class Node { constructor(data) { this .data = data; this .next = null ; } } // Function to remove all occurrences of // head2 in head1 function removeOccurrences(head1, head2) { let dummyHead = new Node(-1); dummyHead.next = head1; let prev = dummyHead; let curr = head1; while (curr !== null ) { if (curr.data === head2.data && curr.next.data === head2.next.data) { prev.next = curr.next.next; curr = prev.next; } else { prev = curr; curr = curr.next; } } return dummyHead.next; } // Function to print the linked list function printList(head) { let result = "" ; while (head !== null ) { result += head.data; if (head.next !== null ) { result += "->" ; } head = head.next; } console.log(result); } // Driver code // Create the linked list head1 let head1 = new Node(2); head1.next = new Node(3); head1.next.next = new Node(4); head1.next.next.next = new Node(5); head1.next.next.next.next = new Node(3); head1.next.next.next.next.next = new Node(4); // Create the linked list head2 let head2 = new Node(3); head2.next = new Node(4); // Function call head1 = removeOccurrences(head1, head2); printList(head1); |
2->5
Time Complexity: O(n), where n is the number of nodes in the linked list head1.
Auxiliary Space: O(1), as we are not using any extra data structures.