โปรแกรม C++ หาโหนดร่วมใน Singly Linked List สองตัว

สมมติว่าเรามี singly-linked list สองตัว เราต้องหาจำนวนโหนดร่วมทั้งหมดใน linked list ทั้งสอง ดังนั้นถ้าสองรายการเป็น [15, 16, 10, 9, 7, 17] และ [15, 16, 40, 6, 9] จะมีโหนดร่วม 3 ตัว

เดินทางผ่านทั้งสองรายการจนถึงปลายรายการโดยใช้สองลูปซ้อนกัน สำหรับทุกโหนดในรายการ ตรวจสอบว่ามันตรงกับโหนดใดของรายการที่สองหรือไม่ หากพบการตรงกัน ให้เพิ่มตัวนับ และสุดท้ายคืนค่าจำนวน

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *next;
};

void prepend(Node** start, int new_data) {
    Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = NULL;
    if ((*start) != NULL){
        new_node->next = (*start);
        *start = new_node;
    }
    (*start) = new_node;
}

int countCommonNodes(Node** start1, Node** start2) {
    Node* ptr = *start1;
    Node* ptr1 = *start2;
    int count = 0;
    while (ptr != NULL) {
        while (ptr1 != NULL) {
            if (ptr->data == ptr1->data) {
                count++;
                break;
            }
            ptr1 = ptr1->next;
        }
        ptr1 = *start2;
        ptr = ptr->next;
    }
    return count;
}

int main() {
    Node* first = NULL;
    Node* second = NULL;
    prepend(&first, 15);
    prepend(&first, 16);
    prepend(&first, 10);
    prepend(&first, 9);
    prepend(&first, 7);
    prepend(&first, 17);
    prepend(&second, 15);
    prepend(&second, 16);
    prepend(&second, 40);
    prepend(&second, 6);
    prepend(&second, 9);
    cout << "Number of common nodes:" << countCommonNodes(&first, &second);
}

ผลลัพธ์

Number of common nodes:3