Nhằm giúp ace nâng cao kỹ năng, kiến thức lập trình, dễ dàng ghi nhớ và hiểu sâu hơn khi đã học lý thuyết về linked list tại series tự học cấu trúc dữ liệu và giải thuật của cafedev. Sau đây là các bài tập có full lời giải và hướng dẫn giải cực chi tiết cho ace trên nhiều ngôn ngữ lập trình khác nhau.
Bài 1: Remove các phần tử trùng lặp trong linked list đã được sắp xếp
Cho một linked list được sắp xếp theo thứ tự tăng dần, hãy viết một hàm loại bỏ bất kỳ nút trùng lặp nào khỏi danh sách bằng cách duyệt qua danh sách chỉ một lần
Cho ví dụ là: {1, 2, 2, 2, 3, 4, 4, 5}
sau khi thực hiện sẽ được kết quả là: {1, 2, 3, 4, 5}
Gợi ý: Vì danh sách được sắp xếp, chúng ta có thể tiến hành rút gọn danh sách và so sánh các nút liền kề. Khi các nút liền kề giống nhau, hãy loại bỏ nút thứ hai. Có một trường hợp phức tạp trong đó nút sau nút tiếp theo cần được lưu ý trước khi xóa.
Hướng dẫn cách xem và tải tài liệu từ trang cafedev tại đây.
Bài giải
Bài 2: Đảo ngược mọi nhóm k nút trong danh sách liên kết đã cho
Cho một danh sách liên kết, đảo ngược mọi nhóm k nút liền kề trong đó với k là số nguyên dương.
Ví dụ:
Input: 1>2>3>4>5>6>7>8>null
k = 3
Output: 3>2>1>6>5>4>8>7>null
k=2
Output: 2>1>4>3>6>5>8>7>null
k = 8
Output: 8>7>6>5>4>3>2>1>null
Gợi ý:
Ý tưởng là xem xét mọi nhóm k nút và đảo ngược đệ quy từng nút một. Cần phải đặc biệt chú ý khi liên kết các nhóm đảo ngược với nhau.
Hướng dẫn cách xem và tải tài liệu từ trang cafedev tại đây.
Bài giải 1
Giải pháp trên trả về con trỏ nút đầu từ hàm. Ngoài ra, chúng ta có thể chuyển con trỏ (tham chiếu) đến nút đầu hàm reverseInGroups() và tránh cập nhật nội bộ con trỏ đầu vào hàm main () như sau:
Hướng dẫn cách xem và tải tài liệu từ trang cafedev tại đây.
Bài giải 2
Bài 3: Di chuyển nút cuối cùng lên phía trước trong Danh sách được liên kết nhất định
Cho một danh sách được liên kết, hãy di chuyển nút cuối cùng của nó lên phía trước.
Ví dụ: Input: 1,2,3,4
Output: 4,1,2,3
Gợi ý: Ý tưởng là làm cho danh sách được liên kết có hình tròn và sau đó ngắt chuỗi trước nút cuối cùng sau khi làm cho danh sách này hướng đến nút cuối cùng.
Hướng dẫn cách xem và tải tài liệu từ trang cafedev tại đây.
Bài giải 1
Chúng ta cũng có thể giải quyết vấn đề này một cách đệ quy. Dưới đây là cách triển khai đệ quy đơn giản của nó như sau:
Bài giải 2
Bài 4: Xóa mọi N nút trong danh sách được liên kết sau khi bỏ qua M nút
Cho một danh sách được liên kết và hai số nguyên dương M và N, xóa mọi N nút trong đó sau khi bỏ qua M nút.
Ví dụ:
1>2>3>4>5>6>7>8>9>10>null
if M = 1, N = 3
Output: 1>5>9>null
if M=2, N=2
Output: 1>2>5>6>9>10>null
Gợ ý: Ý tưởng rất đơn giản. Chúng tôi duyệt qua danh sách đã cho và bỏ qua m nút đầu tiên và xóa n nút tiếp theo trong đó và lặp lại cho các nút còn lại. Giải pháp rất đơn giản nhưng chúng ta cần đảm bảo rằng tất cả các điều kiện biên được xử lý đúng cách trong code.
Bài giải
Bài 5: Hợp nhất hai danh sách liên kết đã sắp xếp thành một
Viết một hàm nhận hai danh sách, mỗi danh sách được sắp xếp theo thứ tự tăng dần và hợp nhất hai danh sách với nhau thành một danh sách theo thứ tự tăng dần và trả về.
Ví dụ:
Input: 1>7>5>4 và 2>6>3>9
Output: 1>2>3>4>5>6>7>9
Gợi ý: Vấn đề có thể được giải quyết bằng vòng lặp hoặc đệ quy. Có nhiều trường hợp cần giải quyết: hoặc ‘a’ hoặc ‘b’ có thể để trống, trong quá trình xử lý, ‘a’ hoặc ‘b’ có thể hết đầu tiên và cuối cùng là vấn đề khởi động danh sách kết quả trống và xây dựng nó lên trong khi đi qua ‘a’ và ‘b’.
Có khá nhiều các giải như sau:
- Sử dụng nút giả
Chiến lược ở đây sử dụng một nút giả tạm thời làm điểm bắt đầu của danh sách kết quả. Đuôi con trỏ luôn trỏ đến nút cuối cùng trong danh sách kết quả, vì vậy việc thêm các Nút mới rất dễ dàng. Nút giả cung cấp cho đuôi một cái gì đó để trỏ đến ban đầu khi danh sách kết quả trống. Nút giả này hiệu quả, vì nó chỉ là tạm thời và nó được cấp phát trong ngăn xếp. Vòng lặp tiếp tục, xóa một nút khỏi ‘a’ hoặc ‘b’ và thêm nó vào đuôi. Khi chúng ta hoàn tất, kết quả là dummy.next.
Bài giải cách 1
- Sử dụng Tham chiếu cục bộ
Giải pháp này có cấu trúc rất giống với giải pháp trên, nhưng nó tránh sử dụng một nút giả. Thay vào đó, nó duy trì một con trỏ struct node ** lastPtrRef , luôn trỏ đến con trỏ cuối cùng của danh sách kết quả. Điều này giải quyết trường hợp tương tự mà nút giả đã làm – xử lý danh sách kết quả khi nó trống. Nếu bạn đang cố gắng tạo một danh sách ở đuôi của nó, bạn có thể sử dụng chiến lược nút giả hoặc nút cấu trúc ** “tham chiếu”.
Bài giải cách 2
- Sử dụng đệ quy
Merge () là một trong những bài toán đệ quy hay trong đó mã giải pháp đệ quy sạch hơn nhiều so với mã lặp. Tuy nhiên, có thể bạn sẽ không muốn sử dụng phiên bản đệ quy cho mã sản xuất vì nó sẽ sử dụng không gian ngăn xếp tỷ lệ với độ dài của danh sách.
Bài giải cách 3
Bài 6: Sắp xếp lại danh sách liên kết theo thứ tự tăng dần (Sắp xếp danh sách liên kết)
Cho một danh sách được liên kết, hãy viết một hàm để sắp xếp lại các nút của nó để chúng được sắp xếp theo thứ tự tăng dần. Nói cách khác, sắp xếp danh sách liên kết.
Gợi ý: Chúng ta có thể sử dụng hàm SortedInsert () để sắp xếp danh sách liên kết. Chúng ta bắt đầu với một danh sách kết quả trống. Lặp lại qua danh sách nguồn và SortedInsert() từng nút của nó vào danh sách kết quả. Hãy cẩn thận lưu ý trường .next trong mỗi nút trước khi chuyển nó vào danh sách kết quả
Bài giải
Bài 7: Chia các nút của danh sách được liên kết đã cho thành các nửa trước và sau
Đưa ra một danh sách, hãy chia nó thành hai danh sách phụ – một cho nửa trước và một cho nửa sau. Nếu số phần tử là số lẻ, phần tử phụ sẽ nằm trong danh sách phía trước.
Ví dụ: Input 2,3,5,7,11, Output: 2,3,5 và 7,11
Gợi ý: Có lẽ chiến lược đơn giản nhất là tính độ dài của danh sách, sau đó sử dụng vòng lặp for để nhảy qua đúng số lượng nút để tìm nút cuối cùng của nửa phía trước, và sau đó cắt danh sách tại điểm đó.
Bài giải
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
