Remove all occurrences of one Linked list in another Linked list in Java
Removing all occurrences of one linked list within another linked list involves traversing through the main linked list and checking if any sublist matches the given pattern. If found, these occurrences need to be removed. A linked list consists of nodes where each node contains a data field and a reference (pointer) to the next node in the sequence.
Example 1
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.
Example 2
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.
Example 3
Input: head1 = 1 -> 2 -> 3 -> 4 -> 5, head2 = 4 -> 5
Output: 1 -> 2 -> 3
Explanation: After removing all occurrences of 4 -> 5 in head1, output is 1 -> 2 -> 3.
Approach 1: Recursive Approach
The recursion approach is used to remove all occurrences of head2 in head1. It checks if the current nodes in head1 and head2 match. If they do, it skips these nodes and continues the search. This process continues recursively until all occurrences are removed.
Algorithm
Step 1: Define a simple Node class with an integer data field and a next pointer.
Step 2: If either head1 or head2 is null, the function returns head1, indicating the end of recursion.
Step 3: It checks if the current nodes in head1 and head2 match. If they do, it recursively calls the function to remove the matched sub-list and moves to the next possible match.
Step 4: If there's no match, it continues searching for matches by moving to the next node in head1.
FileName: RemoveOccurrencesUsingRecursion.java
class Node { int data; Node next; public Node(int x) { data = x; next = null; } } public class RemoveOccurrencesUsingRecursion { // Recursive function to remove occurrences of head2 in head1 public static Node removeOccurrences(Node head1, Node head2) { // Base case: if either head1 or head2 is null, return head1 if (head1 == null || head2 == null) { return head1; } // If the current nodes in head1 and head2 match if (head1.data == head2.data && head1.next.data == head2.next.data) { // Remove occurrences and move to the next possible match return removeOccurrences(head1.next.next, head2); } else { // Otherwise, continue searching for matches head1.next = removeOccurrences(head1.next, head2); 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(); } 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); // Remove occurrences and print the resulting list head1 = removeOccurrences(head1, head2); printList(head1); } }
Output
2->5
Time Complexity: The time complexity of an approach is O(n), where n is the number of nodes. This is because for each node in head1, there might be a need to traverse the entire head2 list to find matches.
Space Complexity: The space complexity of this approach is O(1), as it uses a constant amount of extra space regardless of the input size. The space used is for the recursive stack, which is limited by the depth of recursion and not the size of the input lists.
Approach 2: Using Two Pointers Approach
The two pointers approach used in the given code for removing occurrences of one linked list in another in linked list manipulation.
Algorithm
Step 1: Initialize a dummy node to simplify list manipulation.
Step 2: Traverse head1 using pointers prev, curr1, and curr2, comparing nodes of head1 with nodes of head2.
Step 3: When a match is found, remove the matched sublist from head1.
Step 4: Continue until the end of head1 is reached or all occurrences of head2 are removed.
FileName: RemoveOccurrencesUsingTwoPointers.java
class Node { int data; Node next; public Node(int x) { data = x; next = null; } } public class RemoveOccurrencesUsingTwoPointers { // Function to remove occurrences of head2 in head1 public static Node removeOccurrences(Node head1, Node head2) { // Create a dummy node to simplify list manipulation Node dummy = new Node(0); dummy.next = head1; // Initialize pointers Node prev = dummy; // Pointer to the node before the current node Node curr1 = head1; // Pointer to traverse head1 Node curr2 = head2; // Pointer to traverse head2 // Traverse head1 while (curr1 != null && curr1.next != null) { // If current nodes in head1 and head2 match if (curr1.data == curr2.data && curr1.next.data == curr2.next.data) { // Remove occurrences by adjusting pointers prev.next = curr1.next.next; curr1 = prev.next; } else { // Move to the next node in head1 prev = curr1; curr1 = curr1.next; } } // Return the modified head1 return dummy.next; } // 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(); } 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); // Remove occurrences and print the resulting list head1 = removeOccurrences(head1, head2); printList(head1); } }
Output
2->5
Time Complexity: The time complexity of an approach is O(n), where n is the number of nodes. This is because for each node in head1, there might be a need to traverse the entire head2 list to find matches.
Space Complexity: The space complexity of an algorithm is O(1). This is because it uses a constant amount of extra space regardless of the input size.