So sánh 2 danh sách liên kết (isEqual)

Nguồn: Hỏi đáp học viên Độ khó: Dễ Danh sách liên kết Con trỏ Cấu trúc dữ liệu

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

Viết hàm so sánh 2 danh sách liên kết xem có giống nhau hoàn toàn không, với tham số hàm truyền vào là con trỏ head đầu mỗi danh sách. Cụ thể, viết chương trình gồm:

• struct node: biểu diễn một node trong danh sách liên kết.
• Hàm createLinkedList:
  • Nhận vào kích thước của danh sách liên kết ($\gt 0$).
  • Tạo danh sách liên kết với các giá trị đọc từ đầu vào chuẩn (stdin), mỗi node mới được thêm vào CUỐI danh sách.
  • Trả về con trỏ trỏ tới node đầu tiên của danh sách.
• Hàm isEqual so sánh hai danh sách liên kết:
  • Nhận vào con trỏ head1 của danh sách thứ nhất và con trỏ head2 của danh sách thứ hai.
  • Trả về true khi và chỉ khi 2 danh sách có cùng kích thước và giá trị các node giống hệt nhau (theo đúng thứ tự). Ngược lại trả về false.
• Hàm main đọc kích thước danh sách, gọi hàm createLinkedList để khởi tạo danh sách, rồi gọi hàm để in kết quả.

Yêu cầu: hoàn thành hai hàm createLinkedList và isEqual.

Dữ liệu vào: các giá trị nhập từ đầu vào chuẩn (stdin), mỗi giá trị nằm trong khoảng $(0;\ 5000)$. Cụ thể (theo hàm main cho sẵn): dòng 1 là $n$, dòng 2 là $n$ giá trị của danh sách thứ nhất, dòng 3 là $m$, dòng 4 là $m$ giá trị của danh sách thứ hai.

Kết quả: in ra 1 nếu hai danh sách giống nhau hoàn toàn, ngược lại in ra 0 (vì cout in giá trị bool ra dạng số).

Write a program where:

• struct node: represents a node in linkedlists
• functions createLinkedList:
  • Receive the size of a linked list ($\gt 0$)
  • create a linked list with value from standard input (stdin) a new node is add to the END of the linked list
  • Return a pointer which points to the first node of the linked list.
• Function isEqual compare two linked list:
  • Receive the pointer head1 of the 1st linked list, pointer head2 of the 2nd linked list
  • Return true if and only if 2 the linked lists have identical size, and node value. Otherwise, return false.
• Function main reads the size of the linked list, calls function createLinkedList to Initialize the linked list, then call function print to print all the node's values of the linked list.

Complete function createLinkedList, isEqual

Input:

The value input from standard input (stdin) with value in $(0;\ 5000)$

Test 1 – input

5
1 3 5 7 9
5
1 3 5 7 9

Test 1 – output

1

Khung code cho sẵn của đề (chỉ được cài đặt bên trong 2 hàm createLinkedList và isEqual):

#include <iostream>
using namespace std;
struct node
{
  int data;
  node *next;
};
node *createLinkedList(int n)
{
  // TO DO
}
bool isEqual(node *head1, node *head2)
{
  // TO DO
}
int main()
{
  int n = 0;
  cin >> n;
  node *head1 = createLinkedList(n);
  int m = 0;
  cin >> m;
  node *head2 = createLinkedList(m);
  cout << isEqual(head1, head2) << endl;
  return 0;
}

Một chỗ gõ nhầm trong khung code gốc

Trong ảnh chụp đề, hàm được khai báo tên là createLinkedList nhưng trong main lại gọi createLinkList (thiếu chữ "ed"). Trong bài này mình thống nhất dùng một tên createLinkedList để code biên dịch được.

Lời mở đầu

Đây là câu hỏi của một em học viên nhắn cho mình. Phần tạo danh sách (createLinkedList) thì hôm trước mình đã hướng dẫn rồi, còn cái hàm so sánh 2 danh sách liên kết thì em ấy chưa hiểu đề muốn gì 😅. Mình giải thích qua tin nhắn khá kỹ, có cả mấy kinh nghiệm về con trỏ head mà nhiều bạn mới học hay bị lú, nên viết lại thành bài để nhiều bạn cùng tham khảo luôn. Hy vọng giúp ích được cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Đề nói gì? Đơn giản thôi: trả về true khi 2 danh sách giống nhau hoàn toàn (cùng số node, và node thứ $i$ của danh sách này có data bằng node thứ $i$ của danh sách kia), còn có 1 cái gì đó khác nhau thì trả về false.

Em học viên còn thắc mắc: "lúc nhập vào thì chỉ có 1 list thôi, làm sao lúc so sánh lại tách ra được thành 2 list?". Các bạn nhìn lại hàm main cho sẵn sẽ thấy nó gọi createLinkedList hai lần: lần đầu đọc $n$ rồi $n$ số tạo ra danh sách head1, lần sau đọc $m$ rồi $m$ số tạo ra danh sách head2. Test ví dụ cũng nhập vào cả 2 list đó:

• 5 và 1 3 5 7 9 → danh sách 1: 1 → 3 → 5 → 7 → 9
• 5 và 1 3 5 7 9 → danh sách 2: 1 → 3 → 5 → 7 → 9

Hai danh sách cùng 5 node và từng cặp node đều bằng nhau nên kết quả là 1 (true). Còn nếu danh sách 2 là 1 3 5 7 (thiếu một node) hoặc 1 3 6 7 9 (khác ở node thứ 3) thì đều in 0.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Đếm số node trước rồi so từng node · duyệt 2 lượtCách 2head1, head2 cùng duyệt song song · duyệt 1 lượt

Cách 1Đếm số node trước, rồi so từng node – O(n + m)

Đây là hướng mà em học viên nghĩ ra đầu tiên: "đề yêu cầu size 2 cái linked list phải bằng nhau và các mắt xích trong đó phải giống nhau, nên đầu tiên em đếm số phần tử, xong em mới so sánh từng mắt xích". Code ban đầu của em ấy như sau:

node *current = head1;
int idx = 0;
while(current != nullptr)
{
    current = current->next;
    idx++;
}
int y = 0;
while(head1 == head2){ y++; head1 = head1->next; }
if (y == idx) return 1;
else return 0;

Ý tưởng thì không sai, nhưng code này "vẫn chưa đúng hết test case" vì mấy lỗi sau:

Các lỗi trong code ban đầu

• head1 == head2 là so sánh địa chỉ của 2 con trỏ, không phải so sánh data. Hai danh sách được tạo riêng bằng new thì các node nằm ở vùng nhớ khác nhau, nên điều kiện này gần như luôn sai ⇒ y = 0 ⇒ luôn trả về 0. Phải so head1->data với head2->data.
• Chỉ đếm số node của danh sách 1, không đếm danh sách 2. Nếu danh sách 2 dài hơn (vd 1 3 5 7 9 11) thì vẫn có thể bị kết luận là bằng nhau.
• Vòng while thứ hai chỉ cho head1 đi tiếp mà head2 đứng yên, và cũng không kiểm tra nullptr ⇒ có thể truy cập vào con trỏ rỗng.

Sửa lại cho đúng ý tưởng "đếm trước, so sau" thì ta viết thêm hàm countNode đếm số node của cả hai danh sách. Nếu số node khác nhau thì trả về false luôn; nếu bằng nhau thì cho 2 con trỏ cùng đi, so data từng cặp node:

#include <iostream>
using namespace std;

struct node
{
    int data;
    node *next;
};

node *createLinkedList(int n)
{
    node *head = nullptr, *tail = nullptr;
    for(int i = 0; i < n; i++)
    {
        node *p = new node;
        cin >> p->data;
        p->next = nullptr;
        if(head == nullptr)
            head = tail = p;
        else
        {
            tail->next = p;
            tail = p;
        }
    }
    return head;
}

int countNode(node *head)
{
    int cnt = 0;
    while(head != nullptr)
    {
        cnt++;
        head = head->next;
    }
    return cnt;
}

bool isEqual(node *head1, node *head2)
{
    if(countNode(head1) != countNode(head2)) // lượt duyệt thứ nhất: đếm
        return false;
    while(head1 != nullptr) // lượt duyệt thứ hai: so data
    {
        if(head1->data != head2->data)
            return false;
        head1 = head1->next;
        head2 = head2->next;
    }
    return true;
}

int main()
{
    int n = 0;
    cin >> n;
    node *head1 = createLinkedList(n);
    int m = 0;
    cin >> m;
    node *head2 = createLinkedList(m);
    cout << isEqual(head1, head2) << endl;
    return 0;
}

import sys


class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


def create_linked_list(n, it):
    head = tail = None
    for _ in range(n):
        p = Node(int(next(it)))
        if head is None:
            head = tail = p
        else:
            tail.next = p
            tail = p
    return head


def count_node(head):
    cnt = 0
    while head is not None:
        cnt += 1
        head = head.next
    return cnt


def is_equal(head1, head2):
    if count_node(head1) != count_node(head2):  # lượt duyệt thứ nhất: đếm
        return False
    while head1 is not None:  # lượt duyệt thứ hai: so data
        if head1.data != head2.data:
            return False
        head1 = head1.next
        head2 = head2.next
    return True


it = iter(sys.stdin.read().split())
n = int(next(it))
head1 = create_linked_list(n, it)
m = int(next(it))
head2 = create_linked_list(m, it)
print(1 if is_equal(head1, head2) else 0)

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ dùng vài biến đếm, con trỏ: $O(1)$ (không tính 2 danh sách).
• Thời gian: lượt đầu duyệt hết cả 2 danh sách để đếm: $O(n + m)$; lượt sau duyệt thêm tối đa $n$ node để so data. Tổng $O(n + m)$.

Không gian$O(1)$

Thời gian$O(n + m)$

Cách này chạy đúng, nhưng như mình nói với em ấy: nếu theo giải pháp đi đếm hết các phần tử của 2 list rồi so sánh với nhau, sau đó mới bắt đầu đi so chi tiết data của các phần tử thì cách này dở rồi 😃. Bởi vì bản chất khi đi đếm số lượng phần tử là mình đã duyệt qua từng node rồi, rồi lại phải duyệt lại lần nữa ⇒ duyệt 2 lần. Mình chỉ nên duyệt 1 lần thôi.

Cách 2Cho head1, head2 cùng duyệt song song – O(min(n, m))

Giải pháp tốt nhất nên là lấy chính 2 con trỏ head1, head2 cùng duyệt danh sách. Có thể bắt theo con trỏ head1 duyệt danh sách 1, cứ với mỗi node trong danh sách 1 thì đồng thời con trỏ head2 cũng duyệt node tương ứng bên nó:

• Nếu thấy con trỏ head1 có tồn tại mà con trỏ head2 khi gọi sang node tương ứng bên nó bị nullptr ⇒ danh sách 2 ngắn hơn ⇒ return false.
• Còn nếu head2 có tồn tại thì lúc này so sánh 2 cái data: nếu khác nhau thì return false; còn nếu giống nhau thì tiếp tục cho lần lượt 2 con trỏ duyệt sang node tiếp theo và lặp lại quy trình trên.
• Sau cùng, khi đã duyệt xong list 1 thì vòng lặp kết thúc (vì vòng lặp chạy duyệt theo list 1 mà). Lúc này kiểm tra con trỏ head2 của list 2: nếu nó cũng là nullptr tức là nó cũng đã kết thúc danh sách bên nó ⇒ return true vì 2 danh sách cùng số lượng phần tử như nhau. Còn nếu head2 vẫn còn khác nullptr tức là list 2 chưa kết thúc ⇒ return false, tức là 2 list không khớp số phần tử nhau.

Ý chính

Hai con trỏ đi song song, mỗi bước cùng tiến 1 node. Gặp một trong ba tình huống thì dừng ngay: data khác nhau, list 2 hết trước list 1, hoặc list 1 hết mà list 2 vẫn còn. Không cần biết trước $n$, $m$, và chỉ duyệt mỗi list 1 lần.

Các bạn nhập 2 danh sách vào khung dưới đây rồi bấm Tiếp để xem 2 con trỏ đi song song như thế nào nhé:

Danh sách 1 Danh sách 2

Ví dụ nhanh:

Code của mình ở đây vẫn là "code notepad" gõ thẳng trong tin nhắn cho em học viên thôi 😄, em ấy nộp thử thì đúng hết luôn. Source code để các bạn tham khảo nếu làm theo hướng này:

#include <iostream>
using namespace std;

struct node
{
    int data;
    node *next;
};

node *createLinkedList(int n)
{
    node *head = nullptr, *tail = nullptr;
    for(int i = 0; i < n; i++)
    {
        node *p = new node;
        cin >> p->data;
        p->next = nullptr;
        if(head == nullptr)
            head = tail = p;
        else
        {
            tail->next = p;
            tail = p;
        }
    }
    return head;
}

bool isEqual(node *head1, node *head2)
{
    while(head1 != nullptr)
    {
        if(head2 != nullptr)
        {
            if(head1->data != head2->data)
                return false;
        }
        else
            return false;

        head1 = head1->next;
        head2 = head2->next;
    }

    if(head2 != nullptr)
        return false;

    return true;
}

int main()
{
    int n = 0;
    cin >> n;
    node *head1 = createLinkedList(n);
    int m = 0;
    cin >> m;
    node *head2 = createLinkedList(m);
    cout << isEqual(head1, head2) << endl;
    return 0;
}

import sys


class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


def create_linked_list(n, it):
    head = tail = None
    for _ in range(n):
        p = Node(int(next(it)))
        if head is None:
            head = tail = p
        else:
            tail.next = p
            tail = p
    return head


def is_equal(head1, head2):
    while head1 is not None:
        if head2 is not None:
            if head1.data != head2.data:
                return False
        else:
            return False

        head1 = head1.next
        head2 = head2.next

    if head2 is not None:
        return False

    return True


it = iter(sys.stdin.read().split())
n = int(next(it))
head1 = create_linked_list(n, it)
m = int(next(it))
head2 = create_linked_list(m, it)
print(1 if is_equal(head1, head2) else 0)

Kinh nghiệm: khi nào được lấy chính head để duyệt?

• Với những hàm mà đòi hỏi phải trả về head của danh sách (như createLinkedList) thì nên dùng 1 con trỏ khác (ví dụ con trỏ current, hay tail như trong code trên) để duyệt lần lượt các node. Chứ nếu dùng chính head mà duyệt thì head đã bị thay đổi địa chỉ, như thế thì sau cùng không return được.
• Còn với những hàm mà không trả về head, như trường hợp hàm bool isEqual này chỉ trả về true/false thôi, thì ta không cần tạo ra current để duyệt mà có thể lấy chính head1, head2 duyệt luôn.
• Cũng không sợ bị thay đổi head ở hàm main truyền vào, vì hàm này đang truyền theo kiểu tham trị: bản chất vô hàm là nó đã tạo ra 1 phiên bản con trỏ head_copy = head, và cái head các bạn gọi trong hàm chính là con trỏ head_copy đó; còn head ở hàm main vẫn giữ nguyên địa chỉ ban đầu.
• Chừng nào tham số con trỏ truyền vào là tham chiếu, ví dụ node *&head, thì nếu lấy con trỏ head này duyệt thì con trỏ head ngoài hàm main sẽ bị thay đổi địa chỉ theo, vì lúc này nó không tạo ra phiên bản copy nữa mà đang làm việc trên chính vùng nhớ con trỏ head của hàm main truyền vào.

Khung chạy tay dưới đây chạy đúng từng dòng của code C++ ở trên. Phần đầu là 2 lần gọi createLinkedList để tạo danh sách, các bạn có thể bấm Tiếp nhanh qua phần đó để tới hàm isEqual (dòng 29 – 49):

C++▶ Chạy tay từng dòng codehead1, head2 cùng đi song song, so data từng cặp node, cuối cùng kiểm tra head2 đã hết chưa.

Dữ liệu vào (stdin) – sửa thoải mái5 1 3 5 7 9 5 1 3 5 7 9

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4struct node

5{

6 int data;

7 node *next;

8};

9

10node *createLinkedList(int n)

11{

12 node *head = nullptr, *tail = nullptr;

13 for(int i = 0; i < n; i++)

14 {

15 node *p = new node;

16 cin >> p->data;

17 p->next = nullptr;

18 if(head == nullptr)

19 head = tail = p;

20 else

21 {

22 tail->next = p;

23 tail = p;

24 }

25 }

26 return head;

27}

28

29bool isEqual(node *head1, node *head2)

30{

31 while(head1 != nullptr)

32 {

33 if(head2 != nullptr)

34 {

35 if(head1->data != head2->data)

36 return false;

37 }

38 else

39 return false;

40

41 head1 = head1->next;

42 head2 = head2->next;

43 }

44

45 if(head2 != nullptr)

46 return false;

47

48 return true;

49}

50

51int main()

52{

53 int n = 0;

54 cin >> n;

55 node *head1 = createLinkedList(n);

56 int m = 0;

57 cin >> m;

58 node *head2 = createLinkedList(m);

59 cout << isEqual(head1, head2) << endl;

60 return 0;

61}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: không tạo thêm biến nào ngoài chính 2 tham số con trỏ: $O(1)$ (không tính 2 danh sách).
• Thời gian: mỗi bước 2 con trỏ cùng tiến 1 node, dừng ngay khi gặp chỗ khác nhau hoặc list 1 hết, nên duyệt tối đa $\min(n, m) + 1$ bước. Khi 2 list giống nhau thì mỗi list chỉ duyệt đúng 1 lần.

Không gian$O(1)$

Thời gian$O(\min(n, m))$

Quan trọng không phải là chỉ xem code, mà là xem nó kèm theo những giải thích ở trên để hiểu cho rõ nghĩa. Các bạn nên lấy một tờ giấy vẽ 2 dãy ô vuông tượng trưng cho 2 danh sách rồi dò lại từng bước (hoặc bấm khung chạy tay) nha. Bạn nào còn đang lơ mơ phần con trỏ và struct thì nên ôn lại chắc phần đó trước rồi mới qua danh sách liên kết, sau đó quay lại tự giải lại bài này 😃.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 500 bộ test ngẫu nhiên (2 danh sách dài 1 – 11 node, có cả trường hợp giống hệt, khác 1 node, list này là phần đầu của list kia), so với việc so sánh 2 mảng trực tiếp – khớp hết. Với 2 danh sách $10^6$ node giống nhau: bản C++ chạy khoảng 0.45 giây (phần lớn là thời gian đọc dữ liệu bằng cin), bản Python khoảng 2.5 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇