Remove duplicates from sorted linked list using recursion

A linked list is a sequence of elements connected together. Each list has a header and a sequence of nodes, each of which holds data for the current node and links to the next node. The basic operations of linked lists are insertion, deletion, search and deletion.

Remove duplicates from sorted linked list

One way to delete nodes is to use recursion. The idea is to compare each node with its neighboring nodes and remove duplicate nodes where they are equal.

Our recursive call will return to the next node. So for the next element we will call the recursive function like current_node->next = our_function(node->next).

We trust our recursion and current_node->next now contains the linked list without any duplicate elements.

In the main method we bid on the list from scratch -

Node* head = new Node(5);
head->next = new Node(5);
head->next->next = new Node(6);
head->next->next->next = new Node(7);
head->next->next->next->next = new Node(7);
head->next->next->next->next->next = new Node(7); 

algorithm

The process of using recursion to remove duplicates from a sorted linked list is as follows.

• Step 1 - Create a linked list with all values ​​sorted in order

• Step 2 - If the linked list does not exist, the program terminates.

• Step 3 - If the linked list does exist, compare the next value of the head node with the value in the head node. If both values ​​are the same, remove the header.

• Step 4 - Step 3 is performed recursively, treating each node as a head until the list removes all duplicate values ​​from itself .

• Step 5 - The output obtained is a sorted linked list with different values

Example

For example, we have a sorted linked list with the following values ​​-

1->1->1->2->3->3->4

Let's look at a C program that will remove duplicates from the above sorted linked list using recursion -

#include <iostream>
using namespace std;
class Node {
   public:
   int data;
   Node* next;
   Node(int data) {
   this->data = data;
   next = NULL;
   }
};
Node* solve(Node* head) {
   if (head == NULL)
   return NULL;
   head->next = solve(head->next);
   if (head->next != NULL && head->next->data == head->data) {
      Node* temp = head->next;
      delete head;
      return temp;
   }
   return head;
}
void printList(Node* node) {
   while (node != NULL) {
      cout << node->data << (node->next == NULL ? "" : "->");
      node = node->next;
   }
}
int main() {
   Node* head = new Node(1);
   head->next = new Node(1);
   head->next->next = new Node(1);
   head->next->next->next = new Node(2);
   head->next->next->next->next = new Node(3);
   head->next->next->next->next->next = new Node(3);
   head->next->next->next->next->next->next = new Node(4);
   cout << "Linked list before: ";
   printList(head);
   head = solve(head);
   cout << "\nLinked list after: ";
   printList(head);
   return 0;
}

After that, we check whether the current node is included in the linked list. If the satisfying linked list we get from current node -> next node has the same value as that node, we don't include that node; otherwise, we include it.

Note - When the current node is NULL, we return the base condition of the recursion.

Output

Linked list before: 1->1->1->2->3->3->4
Linked list after: 1->2->3->4

in conclusion

As we saw with the recursive call, we trust that the next call will achieve the expected result of the rest of the problem. We just solved the current subproblem. With this in mind, we check if the current element can be contained and hand the rest of the linked list over to our recursive call, trusting it to give us a valid linked list from that point on. When we traverse the entire linked list, the time complexity of our method is O(n).

The above is the detailed content of Remove duplicates from sorted linked list using recursion. For more information, please follow other related articles on the PHP Chinese website!