Danh sách liên kết là một dãy các phần tử được kết nối với nhau. Mỗi danh sách có một đầu và một loạt các nút và mỗi nút có dữ liệu của nút hiện tại và liên kết đến nút tiếp theo. Các thao tác cơ bản của danh sách liên kết là chèn, xóa, tìm kiếm và xóa
Loại bỏ các bản sao khỏi danh sách liên kết được sắp xếp
Một cách để loại bỏ các nút là sử dụng đệ quy. Ý tưởng là so sánh từng nút với nút liền kề của nó và xóa nút trùng lặp mà chúng bằng nhau
Cuộc gọi đệ quy của chúng tôi sẽ đưa chúng tôi trở lại nút tiếp theo. Vì vậy, đối với phần tử tiếp theo, chúng ta sẽ gọi hàm đệ quy của mình như current_node->next = our_function[node->next]
Chúng tôi tin tưởng vào đệ quy của mình rằng current_node->next hiện chứa danh sách được liên kết, không có bất kỳ phần tử trùng lặp nào
Trong phương pháp chính, chúng tôi đang đặt giá thầu danh sách từ đầu là -
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];
thuật toán
Quy trình tiếp theo là phương pháp loại bỏ các mục trùng lặp khỏi danh sách liên kết được sắp xếp bằng cách sử dụng đệ quy như sau
Bước 1 - Một danh sách được liên kết được tạo với tất cả các giá trị được sắp xếp theo thứ tự
Bước 2 - Nếu danh sách được liên kết không tồn tại, chương trình sẽ kết thúc
Bước 3 - Nếu danh sách được liên kết tồn tại, giá trị tiếp theo của nút đầu được so sánh với giá trị trong nút đầu. Nếu hai giá trị giống nhau, phần đầu sẽ bị xóa
Bước 4 - Bước 3 được thực hiện đệ quy, coi mỗi nút là phần đầu cho đến khi danh sách loại bỏ tất cả các giá trị trùng lặp khỏi chính nó
Bước 5 - Đầu ra thu được là một danh sách được liên kết được sắp xếp với các giá trị riêng biệt
Ví dụ
Ví dụ: chúng tôi có một danh sách được liên kết được sắp xếp với các giá trị sau -
1->1->1->2->3->3->4
Chúng ta hãy xem một chương trình C++ sẽ loại bỏ các bản sao khỏi danh sách liên kết được sắp xếp ở trên bằng cách sử dụng đệ quy -
#include 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 data 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 1->1->2->3->3->4 Linked list after: 1->2->3->4
Phần kết luận
Như chúng ta thấy trong các lời gọi đệ quy, chúng ta tin tưởng lời gọi tiếp theo sẽ đạt được kết quả mong muốn cho phần còn lại của bài toán. Chúng tôi vừa giải quyết vấn đề con hiện tại của chúng tôi. Hãy ghi nhớ điều này, chúng tôi đã kiểm tra xem chúng tôi có thể bao gồm phần tử hiện tại hay không và đưa phần còn lại của danh sách được liên kết vào lệnh gọi đệ quy của chúng tôi và tin tưởng vào nó để cung cấp cho chúng tôi một danh sách được liên kết hợp lệ từ đó trở đi. Độ phức tạp về thời gian của phương pháp của chúng tôi là O[n] khi chúng tôi duyệt qua toàn bộ danh sách được liên kết
Viết hàm removeDuplicates[] lấy danh sách được sắp xếp theo thứ tự không giảm dần và xóa mọi nút trùng lặp khỏi danh sách. Danh sách chỉ nên duyệt qua một lần.
Ví dụ: nếu danh sách được liên kết là 11->11->11->21->43->43->60 thì removeDuplicates[] sẽ chuyển đổi danh sách thành 11->21->43->60.
Khuyến khích. Vui lòng thử cách tiếp cận của bạn trên {IDE} trước, trước khi chuyển sang giải pháp
thuật toán. Duyệt qua danh sách một cách đệ quy từ đầu [hoặc bắt đầu] đến cuối và sau khi hoàn thành các cuộc gọi đệ quy, hãy so sánh nút tiếp theo [nút được trả về] và nút hiện tại [đầu]. Nếu dữ liệu của cả hai nút bằng nhau thì trả về nút tiếp theo [đầu-> tiếp theo] nếu không thì trả về nút hiện tại [đầu]
Thực hiện. Các chức năng khác ngoài removeDuplicates[] chỉ để tạo danh sách được liên kết và kiểm tra removeDuplicates[].