Độ khó: Dễ (1/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

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 (~> 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.

Khung code cho sẵn của đề (chỉ cài đặt bên trong 2 hàm createLinkedList và isEqual; nộp cả chương trình hoàn chỉnh):

#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;
}

Dữ liệu vào

• 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ố).

Giới hạn

• ~1 \le n, m \le 10^5~.
• Mỗi giá trị nằm trong khoảng ~(0;\ 5000)~.

Sample Input 1

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

Sample Output 1

1

Sample Input 2

5
1 3 5 7 9
4
1 3 5 7

Sample Output 2

0

Giải thích

Ví dụ 1: 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). Ví dụ 2: danh sách 2 thiếu một node nên kết quả là 0.