cpp-139Đọc toàn bộ đề miễn phí

Tìm Điểm Giao Của Hai Danh Sách Liên Kết (Intersection of Two Lists)

Hai danh sách liên kết A và B có thể hợp nhất tại một nút chung X, sau đó tiếp tục đi chung một đoạn đuôi đến hết danh sách (hình dạng chữ Y).

C++Trung bình25 phút

Tiến độ của tôi ở bài này

Điểm được lưu vào tài khoản sau khi chấm bài.

Đang tải điểm của bạn…

Kiến thức và chủ đề

Linked ListTwo Pointers

Kiến thức tiên quyết: Length Difference Technique, Two Pointers.

Nội dung đề bài3 cấp độ gợi ýPhân tích lời giảiCode tham khảo

Nội dung đề bài

Mô tả bài toán

Hai danh sách liên kết $A$ và $B$ có thể hợp nhất tại một nút chung $X$ , sau đó tiếp tục đi chung một đoạn đuôi đến hết danh sách (hình dạng chữ Y).

Mô hình bài toán:

Danh sách $A$ gồm phần riêng $a 1, a 2, \dots, a lenA$ nối vào phần chung $c 1, c 2, \dots, c k$ .
Danh sách $B$ gồm phần riêng $b 1, b 2, \dots, b lenB$ nối vào chính phần chung $c 1, c 2, \dots, c k$ .
Điểm giao đầu tiên chính là giá trị $c 1$ . Nếu hai danh sách hoàn toàn độc lập (không có phần chung, $k = 0$ ), điểm giao không tồn tại và in ra -1.

Hãy tìm giá trị của điểm giao đầu tiên $c 1$ bằng thuật toán đạt độ phức tạp $O(|A| + |B|)$ thời gian và $O(1)$ bộ nhớ phụ trợ.

Quy ước nộp bài

Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Input

Dòng đầu chứa ba số nguyên $lenA, lenB, k$ ( $0 \leq lenA, lenB \leq 105, 0 \leq k \leq 105, lenA + lenB + k \geq 1$ ).
Dòng thứ hai chứa $lenA$ số nguyên phần riêng của $A$ .
Dòng thứ ba chứa $lenB$ số nguyên phần riêng của $B$ .
Dòng thứ tư chứa $k$ số nguyên phần chung của cả hai danh sách (nếu $k > 0$ ).

Output

In ra giá trị của nút giao đầu tiên $c 1$ , hoặc -1 nếu $k = 0$ .

Ràng buộc

Thời gian chạy tối đa: 1000ms.
Giới hạn bộ nhớ: 256MB.
Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.

Ví dụ 1

Input

Output

Giải thích

Dữ liệu kiểm thử mẫu và kết quả thực thi theo yêu cầu.

3 cấp độ gợi ýMở dần khi bạn thật sự cần hỗ trợ.

Phân tích lời giảiGiải thích hướng tư duy và thuật toán.

Code tham khảoDùng để đối chiếu sau khi tự làm.

Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.

Góp ý & báo lỗi bài tập

Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.

Tiến độ của tôi ở bài này

Kiến thức và chủ đề

Nội dung đề bài

Mô tả bài toán

Quy ước nộp bài

Input

Output

Ràng buộc

Ví dụ 1

Input

Output

Giải thích

Bài tập liên quan cùng chuyên đề

Góp ý & báo lỗi bài tập