Remove all occurrences of one Linked list in another Linked list

Last Updated : 17 Aug, 2023

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);

Output

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.