40 câu hỏi và câu trả lời phỏng vấn hàng đầu về danh sách liên kết (2026)
Sarah Chen
Việc chuẩn bị cho một cuộc phỏng vấn về cấu trúc dữ liệu đòi hỏi sự tập trung vào các bài toán thực tế. Các câu hỏi phỏng vấn về danh sách liên kết sẽ tiết lộ chiều sâu trong khả năng giải quyết vấn đề, logic con trỏ, nhận thức về bộ nhớ và cách ứng viên suy luận qua các trường hợp ngoại lệ.
Nắm vững danh sách liên kết mở ra nhiều cơ hội nghề nghiệp trong các nhóm sản phẩm, nền tảng và kỹ thuật hệ thống. Kinh nghiệm thực tế giúp xây dựng chuyên môn kỹ thuật vững chắc, tư duy phân tích và thói quen lập trình sạch sẽ. Từ sinh viên mới ra trường đến các chuyên gia cấp cao, kỹ năng này hỗ trợ việc gỡ lỗi thực tế, phân tích hiệu năng, hướng dẫn các bạn trẻ và cộng tác với quản lý trong việc xây dựng các giải pháp có khả năng mở rộng bằng cách sử dụng các khái niệm nâng cao từ kinh nghiệm. Đọc thêm ...
👉 Tải xuống PDF miễn phí: Câu hỏi và câu trả lời phỏng vấn về danh sách liên kết
Các câu hỏi và câu trả lời phỏng vấn hàng đầu về danh sách liên kết
1) Hãy giải thích danh sách liên kết là gì và nó khác với mảng như thế nào.
A danh sách liên kết Danh sách liên kết là một cấu trúc dữ liệu tuyến tính trong đó các phần tử, được gọi là các nút, được kết nối với nhau bằng con trỏ hoặc tham chiếu. Mỗi nút chứa dữ liệu và một con trỏ/tham chiếu đến nút tiếp theo trong danh sách. Không giống như mảng, danh sách liên kết không lưu trữ các phần tử trong bộ nhớ liền kề.
Những điểm khác biệt chính giữa danh sách liên kết và mảng:
| Tính năng | Danh sách liên kết | Mảng |
|---|---|---|
| Cấp phát bộ nhớ | Năng động | tĩnh |
| Thời gian truy cập phần tử | O (n) | O (1) |
| Chèn/Xóa | Hiệu quả (ở bất kỳ vị trí nào) | Tốn kém (cần phải di dời) |
| Chi phí bộ nhớ | Thêm không gian cho con trỏ | Không phát sinh thêm chi phí con trỏ. |
Tóm lại, danh sách liên kết đánh đổi việc chèn nhanh hơn và kích thước động lấy việc truy cập ngẫu nhiên chậm hơn và chi phí bộ nhớ bổ sung do con trỏ.
2) Danh sách liên kết có những loại nào?
Có một số loại danh sách liên kếtvà người phỏng vấn thường yêu cầu bạn phân biệt giữa chúng:
- Danh sách liên kết đơn: Mỗi nút chỉ trỏ đến nút kế tiếp.
- Danh sách liên kết đôi: Các nút có hai con trỏ: một đến nút kế tiếp và một đến nút trước đó.
- Danh sách liên kết vòng tròn: Nút cuối cùng trỏ ngược về nút đầu tiên, tạo thành một vòng lặp.
- Danh sách liên kết vòng kép: Kết hợp cả danh sách vòng và danh sách liên kết đôi.
Mỗi loại danh sách liên kết có các trường hợp sử dụng khác nhau dựa trên nhu cầu duyệt và bộ nhớ. Ví dụ, danh sách liên kết đôi cho phép duyệt ngược dễ dàng với chi phí là thêm các con trỏ.
3) Làm thế nào để đảo ngược một danh sách liên kết đơn? (Phương pháp lập trình)
RevĐảo ngược danh sách liên kết là một câu hỏi phỏng vấn kinh điển. Mục tiêu là thay đổi hướng của con trỏ sao cho danh sách được đảo ngược tại chỗ mà không cần cấp phát thêm nút mới.
Ý chính:
Hãy sử dụng ba con trỏ — prev, currvà next — và lặp qua danh sách. Ở mỗi bước, hãy chuyển hướng. curr.next đến prevSau đó, tăng tất cả các con trỏ.
ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev; // New head
}
Điều này biến đổi cấu trúc liên kết mà không cần thêm không gian và chạy trong O (n) thời gian.
4) Giải thích kỹ thuật hai con trỏ để tìm phần tử giữa của một danh sách liên kết.
Cách hiệu quả nhất để tìm nút giữa của một danh sách liên kết là sử dụng hai con trỏ:
- A con trỏ chậm Di chuyển từng nút một.
- A con trỏ nhanh Di chuyển hai nút cùng một lúc.
Khi con trỏ nhanh đạt đến điểm cuối, con trỏ chậm sẽ ở điểm giữa. Kỹ thuật này hoạt động trong O (n) thời gian mà không cần thêm không gian.
5) Làm thế nào để phát hiện chu trình trong danh sách liên kết?
Phát hiện chu kỳ là một bài toán kinh điển khác. Giải pháp tiêu chuẩn sử dụng Thuật toán Rùa và Thỏ của Floyd:
- Di chuyển
slow pointerMột bước tại một thời điểm. - Di chuyển
fast pointerTừng bước một, mỗi lần hai bước. - Nếu danh sách có chu kỳ, hai con trỏ sẽ gặp nhau.
Nếu con trỏ nhanh đạt đến nullDanh sách này không có chu kỳ. Phương pháp này chạy trong O (n) thời gian và O (1) không gian.
6) Danh sách liên kết có những ưu điểm và nhược điểm gì?
Danh sách liên kết mang lại một số lợi ích và hạn chế:
| Ưu điểm | Nhược điểm |
|---|---|
| Kích thước động | Không có quyền truy cập ngẫu nhiên |
| Thêm/xóa dễ dàng | Bộ nhớ bổ sung cho con trỏ |
| Hiệu quả cho việc xử lý dữ liệu ngày càng tăng. | Hiệu năng bộ nhớ đệm kém |
Danh sách liên kết hoạt động tốt với dữ liệu động nhưng có thể chậm hơn mảng khi truy cập phần tử vì mỗi lần truy cập đều yêu cầu duyệt từ đầu.
7) Làm thế nào để hợp nhất hai danh sách liên kết đã được sắp xếp?
Ghép hai danh sách đã được sắp xếp là một bài toán phỏng vấn phổ biến khác. Ý tưởng là duyệt đồng thời cả hai danh sách và xây dựng một danh sách mới đã được sắp xếp bằng cách chọn nút nhỏ hơn từ một trong hai danh sách ở mỗi bước.
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
Phương pháp này giữ nguyên thứ tự đã sắp xếp và chạy trong O(n + m) thời gian cho các danh sách có độ dài n và m.
8) Hãy giải thích cách xóa nút thứ N khỏi cuối danh sách liên kết.
Kỹ thuật hiệu quả nhất sử dụng hai con trỏ Ngăn cách bởi n nút. Di chuyển con trỏ thứ nhất n bước, sau đó di chuyển cả hai con trỏ cho đến khi con trỏ thứ nhất đến đích. Con trỏ thứ hai lúc đó sẽ nằm ngay trước nút đích.
Điều này giúp tránh việc tính toán độ dài danh sách một cách riêng biệt và hoàn thành trong O (n) thời gian. Nó cũng xử lý các trường hợp ngoại lệ như xóa nút đầu tiên.
9) Độ phức tạp thời gian để truy cập phần tử thứ k trong danh sách liên kết là gì?
Truy cập vào kPhần tử thứ i trong danh sách liên kết yêu cầu duyệt từ đầu danh sách cho đến khi đến cuối danh sách. knút thứ i. Vì danh sách liên kết không cung cấp chỉ mục trực tiếp, nên điều này tốn kém. O (n) thời gian trong trường hợp xấu nhất.
Ngược lại, mảng hỗ trợ truy cập trực tiếp bằng chỉ mục. O (1) thời gian.
10) Tại sao bạn lại sử dụng danh sách liên kết thay vì mảng?
Danh sách liên kết đặc biệt hữu ích khi:
- Bạn dự đoán sẽ có nhiều thao tác chèn và xóa tại các vị trí ngẫu nhiên.
- Bạn không biết trước kích thước dữ liệu của mình.
- Sự phân mảnh bộ nhớ khiến việc phân bổ bộ nhớ liền kề trở nên khó khăn.
Chúng hỗ trợ cấp phát bộ nhớ động hiệu quả và thao tác chèn/xóa với thời gian không đổi ở cuối danh sách hoặc với tham chiếu nút đã biết — những ưu điểm mà mảng không thể sánh được.
11) Danh sách liên kết có những ứng dụng thực tế nào?
Danh sách liên kết được sử dụng rộng rãi trong các hệ thống mà ở đó cấp phát bộ nhớ động, chèn thường xuyên, hoặc là cấu trúc dữ liệu kích thước thay đổi Chúng là cần thiết. Chúng được triển khai trong một số khái niệm và ứng dụng cốt lõi của khoa học máy tính, chẳng hạn như:
- Quản lý bộ nhớ động (được sử dụng trong hệ điều hành)
- Chức năng hoàn tác/làm lại trong trình soạn thảo văn bản
- chuỗi bảng băm để giải quyết các va chạm
- Điều hướng danh sách phát nhạc hoặc video
- Biểu diễn kề nhau của đồ thị
- Các phép toán số học đa thức
Những ví dụ này làm nổi bật cách danh sách liên kết cung cấp tính linh hoạt và khả năng thao tác hiệu quả với các chuỗi, trong khi việc thay đổi kích thước mảng sẽ tốn kém.
12) Giải thích sự khác biệt giữa danh sách liên kết đơn và danh sách liên kết đôi.
| Tính năng | Danh sách liên kết đơn | Danh sách được liên kết gấp đôi |
|---|---|---|
| con trỏ | 1 (chỉ nút tiếp theo) | 2 (trước và sau) |
| Truyền tải | Chỉ một hướng | Cả hai hướng |
| Sử dụng bộ nhớ | Less (chỉ một con trỏ) | Thêm nữa (gợi ý bổ sung) |
| xóa | Khó hơn (cần nút trước đó) | Dễ dàng hơn |
| Sử dụng ví dụ | Triển khai ngăn xếp | Điều hướng lịch sử trình duyệt |
A danh sách liên kết kép Nó linh hoạt hơn nhưng tiêu tốn thêm bộ nhớ. Ngược lại, danh sách liên kết đơn Chúng có trọng lượng nhẹ và hiệu quả cho việc di chuyển theo một hướng.
13) Làm thế nào để loại bỏ các phần tử trùng lặp khỏi một danh sách liên kết đã được sắp xếp?
Khi danh sách liên kết đã được sắp xếp, các phần tử trùng lặp sẽ nằm cạnh nhau.
Duyệt qua danh sách và so sánh dữ liệu của từng nút với nút kế tiếp. Nếu chúng trùng khớp, hãy bỏ qua nút tiếp theo.
void removeDuplicates(ListNode head) {
ListNode current = head;
while (current != null && current.next != null) {
if (current.val == current.next.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
}
Phức tạp: Thời gian O(n) và không gian O(1).
Đối với các danh sách chưa được sắp xếp, có thể sử dụng HashSet để theo dõi các giá trị đã thấy.
14) Sự khác biệt giữa danh sách liên kết tuyến tính và danh sách liên kết vòng là gì?
| Tính năng | Danh sách liên kết tuyến tính | Danh sách liên kết hình tròn |
|---|---|---|
| Nút cuối cùng | Trỏ trỏ đến NULL | Chỉ vào nút đầu |
| Truyền tải | Kết thúc khi next == NULL |
Di chuyển liên tục |
| Trường hợp sử dụng | Ngăn xếp, Hàng đợi | Lập lịch luân phiên |
| phức tạp | Đơn giản hơn | Xử lý phức tạp hơn |
Danh sách vòng tròn đặc biệt hữu ích trong các ứng dụng như lập lịch CPU, nơi các tiến trình được thực thi theo chu kỳ.
15) Làm thế nào để tìm điểm giao nhau của hai danh sách liên kết?
Để xác định xem hai danh sách liên kết đơn có giao nhau hay không:
- Tìm độ dài của cả hai danh sách.
- Di chuyển con trỏ của danh sách dài hơn đi một lượng bằng hiệu số độ dài giữa hai phần tử.
- Duyệt đồng thời cả hai danh sách cho đến khi các nút giống hệt nhau.
Ngoài ra, một Bộ băm có thể được sử dụng để lưu trữ các nút đã truy cập với không gian O(n).
Cách tiếp cận này hiệu quả và thường được hỏi trong các cuộc phỏng vấn cấp cao.
16) Làm thế nào để kiểm tra xem hai danh sách liên kết có giống hệt nhau hay không?
Hai danh sách liên kết được coi là giống hệt nhau nếu:
- Chúng có cùng số lượng nút.
- Các giá trị nút tương ứng có thứ tự giống hệt nhau.
Thuật toán:
- Duyệt qua cả hai danh sách cùng lúc.
- So sánh dữ liệu của từng nút.
- Nếu tất cả các cặp đều khớp và cả hai đều trả về giá trị NULL, thì chúng giống hệt nhau.
Độ phức tạp về thời gian: O (n)
Độ phức tạp không gian: O (1)
17) Rò rỉ bộ nhớ trong ngữ cảnh của danh sách liên kết là gì?
A bộ nhớ bị rò rỉ Xảy ra khi các nút được cấp phát động không được giải phóng sau khi sử dụng.
Trong danh sách liên kết, nếu delete or free() Phương thức này không được gọi trên các nút đã bị xóa khỏi danh sách, do đó bộ nhớ vẫn bị chiếm dụng ngay cả khi không còn truy cập được nữa.
Ví dụ, việc không giải phóng các nút đã xóa trong C/C++ Điều này dẫn đến tình trạng cạn kiệt bộ nhớ dần dần, gây ra hiện tượng hệ thống chậm hoặc bị treo.
Việc dọn dẹp đúng cách bằng cách sử dụng hàm hủy hoặc giải phóng bộ nhớ rõ ràng sẽ tránh được vấn đề này.
18) Hãy giải thích cách triển khai một ngăn xếp sử dụng danh sách liên kết.
Trong một ngăn xếpCác phần tử được sắp xếp theo thứ tự LIFO (Vào sau, ra trước).
Danh sách liên kết là lý tưởng vì việc chèn và xóa phần tử diễn ra hiệu quả ở đầu danh sách.
Operaý kiến:
- Đẩy: Thêm nút mới vào đầu.
- Nhạc pop: Loại bỏ nút khỏi đầu.
- Nhìn trộm: Trả về dữ liệu đầu.
Ưu điểm:
Không cần mảng có kích thước cố định; kích thước mảng sẽ tự động tăng lên khi các phần tử được thêm vào.
19) Làm thế nào có thể sử dụng danh sách liên kết để triển khai hàng đợi?
Trong một hàng đợiCác phần tử được sắp xếp theo thứ tự FIFO (Vào trước, Ra trước).
Sử dụng danh sách liên kết trong các trường hợp sau:
- Thêm vào hàng đợi (Insert): Thêm nút ở cuối.
- Dequeue (Remove): Xóa nút khỏi đầu trang.
Điều này cho phép cả hai hoạt động trong O (1) thời gian với hai con trỏ — front và rear.
Nó thường được sử dụng trong lập lịch trình quy trình và hệ thống xếp hàng máy in.
20) Sự khác biệt giữa danh sách mảng và danh sách liên kết là gì? Java?
| Yếu tố | Lập danh sách | Danh sách liên kết |
|---|---|---|
| Bảo quản | Mảng động | Danh sách liên kết kép |
| Thời gian truy cập | O (1) | O (n) |
| Chèn/Xóa | Đắt đỏ ở khu vực trung lưu | Hiệu quả ở các đầu |
| Chi phí bộ nhớ | Less | Thêm (những lời khuyên bổ sung) |
| Trường hợp sử dụng | Truy cập thường xuyên | Chèn/xóa thường xuyên |
Ví dụ: Sử dụng ArrayList đối với các thao tác tra cứu nhiều, và LinkedList khi các thao tác chèn/xóa chiếm ưu thế.
21) Làm thế nào để làm phẳng một danh sách liên kết nhiều cấp?
A danh sách liên kết nhiều cấp có thể chứa các nút có cả hai đặc điểm trên next và child Các con trỏ (mỗi con trỏ đến một danh sách liên kết khác). Mục tiêu là làm phẳng tất cả các nút thành một danh sách liên kết một cấp.
Tiếp cận:
- Sử dụng ngăn xếp or Hàm đệ quy.
- Bắt đầu từ nút đầu.
- Nếu một nút có
child, đẩy nónextthêm nút vào ngăn xếp và tạochildasnext. - Tiếp tục cho đến khi ngăn xếp trống.
Độ phức tạp về thời gian: O (n)
Không gian phức tạp: Độ phức tạp O(n) đối với đệ quy/ngăn xếp.
Ví dụ (về mặt khái niệm):
1 - 2 - 3
|
4 - 5
Flattened → 1 → 2 → 4 → 5 → 3
Câu hỏi này đánh giá sự hiểu biết của bạn về đệ quy và thao tác con trỏ.
22) Làm thế nào để sao chép một danh sách liên kết có con trỏ ngẫu nhiên?
Mỗi nút trong danh sách liên kết đặc biệt này có hai con trỏ:
next→ trỏ đến nút tiếp theo.random→ trỏ đến bất kỳ nút nào tùy ý.
Thuật toán (3 bước):
- Chèn các nút được sao chép vào giữa các nút gốc.
- Gán con trỏ ngẫu nhiên cho các bản sao (
clone.random = original.random.next). - Tách hai danh sách ra.
Điều này giúp tránh lãng phí không gian cho bảng băm và chạy nhanh hơn. O (n) thời gian với O (1) không gian bổ sung.
Ca sử dụng: Sao chép sâu các cấu trúc dữ liệu phức tạp (ví dụ: đồ thị hoặc tham chiếu đối tượng).
23) Danh sách bỏ qua (skip list) là gì và nó có liên quan như thế nào đến danh sách liên kết (linked list)?
A bỏ qua danh sách Đây là cấu trúc danh sách liên kết nhiều lớp cho phép tìm kiếm, chèn và xóa nhanh chóng (tương tự như cây cân bằng).
| Operasản xuất | Thời gian trung bình | Trường hợp xấu nhất |
|---|---|---|
| Tìm kiếm | O (log n) | O (n) |
| Chèn/Xóa | O (log n) | O (n) |
Nó bao gồm nhiều cấp độ, trong đó các cấp độ cao hơn "bỏ qua" một số nút, giúp cải thiện hiệu quả tìm kiếm.
Ví dụ: Được sử dụng trong các cơ sở dữ liệu như Redis và các triển khai map đồng thời.
24) Làm thế nào để phát hiện một chuỗi đối xứng trong một danh sách liên kết?
Một danh sách liên kết được gọi là palindrome nếu nó đọc giống nhau từ đầu đến cuối.
Thuật toán:
- Tìm phần tử ở giữa danh sách.
- Revtrong hiệp hai.
- So sánh hai nửa từng nút một.
Nếu tất cả các nút tương ứng đều trùng khớp, đó là một chuỗi đối xứng.
Ví dụ:
1 → 2 → 3 → 2 → 1 → ✅ Chuỗi đối xứng
1 → 2 → 3 → 4 → ❌ Không phải là chuỗi đối xứng
Độ phức tạp về thời gian: O (n)
Không gian phức tạp: O (1)
25) Làm thế nào để loại bỏ vòng lặp trong danh sách liên kết?
Nếu tồn tại vòng lặp (sử dụng phương pháp phát hiện chu kỳ của Floyd), hãy loại bỏ nó bằng các bước sau:
- Xác định điểm giao nhau của các con trỏ chậm và nhanh.
- Di chuyển con trỏ chuột lên phía đầu.
- Di chuyển cả hai con trỏ từng bước một cho đến khi chúng gặp nhau tại điểm đó. nút bắt đầu vòng lặp.
- Đặt nút trước đó
nextđếnnull.
Cách tiếp cận này đảm bảo không sử dụng thêm bộ nhớ trong quá trình giải quyết các chu kỳ.
26) Có những cách nào khác nhau để biểu diễn danh sách liên kết trong bộ nhớ?
Danh sách liên kết có thể được biểu diễn dưới dạng ba cách chính:
| Loại đại diện | Mô tả Chi tiết | Sử dụng ví dụ |
|---|---|---|
| Các nút động | Mỗi nút được phân bổ và liên kết động. | C, C++ |
| Biểu diễn mảng tĩnh | Sử dụng chỉ số mảng thay vì con trỏ. | Hệ thống nhúng |
| Các đối tượng được liên kết | Biểu diễn hướng đối tượng bằng các lớp | Java, Python |
Mỗi phương pháp phù hợp với các môi trường khác nhau — ví dụ, danh sách dựa trên mảng được sử dụng khi việc thao tác con trỏ bị hạn chế.
27) Làm thế nào để tìm độ dài của một danh sách liên kết (phương pháp lặp và đệ quy)?
Phương pháp tiếp cận lặp lại:
int getLength(ListNode head) {
int count = 0;
while (head != null) {
count++;
head = head.next;
}
return count;
}
Phương pháp đệ quy:
int getLength(ListNode head) {
if (head == null) return 0;
return 1 + getLength(head.next);
}
Cả hai cách tiếp cận đều có O (n) độ phức tạp thời gian; đệ quy cộng thêm O (n) Chi phí bộ nhớ phát sinh do ngăn xếp cuộc gọi.
28) Hãy giải thích khái niệm về danh sách liên kết đôi vòng tròn bằng một ví dụ.
Trong một danh sách liên kết đôi vòng trònMỗi nút có hai liên kết — một đến nút tiếp theo và một đến nút trước đó — và liên kết của nút cuối cùng... next chỉ vào đầu, trong khi đầu prev Trỏ đến nút cuối cùng.
Các trường hợp sử dụng mẫu:
- Hệ điều hành thời gian thực (lập lịch luân phiên)
- danh sách phát nhạc lặp lại
- Điều hướng giữa các tab hoặc slide
Ưu điểm:
- Di chuyển hai chiều.
- Không có tham chiếu null.
- Chèn và xóa dữ liệu hiệu quả.
29) Làm thế nào để xóa các nút xen kẽ trong một danh sách liên kết?
Thuật toán:
- Bắt đầu từ đầu.
- Xóa mỗi nút thứ hai bằng cách điều chỉnh con trỏ.
- Tiếp tục cho đến khi hết danh sách.
Ví dụ:
Input: 1 → 2 → 3 → 4 → 5 Output: 1 → 3 → 5
Phức tạp:
- Thời gian: O(n)
- Không gian: O(1)
Điều này giúp kiểm tra sự hiểu biết về tính an toàn khi duyệt con trỏ và xóa dữ liệu.
30) Làm thế nào để tìm được nút thứ n từ đầu và từ cuối của một danh sách liên kết?
Từ đầu: Duyệt qua danh sách cho đến khi count = n.
Từ cuối bài: Sử dụng hai con trỏ.
- Di chuyển con trỏ đầu tiên tiến lên n bước.
- Di chuyển cả hai đồng thời cho đến khi cái đầu tiên đạt đến vị trí null.
- Con trỏ thứ hai hiện đang trỏ đến nút thứ n tính từ cuối.
Độ phức tạp về thời gian: O (n)
Không gian phức tạp: O (1)
Cách tiếp cận này tránh việc tính toán độ dài riêng biệt, giúp nâng cao hiệu quả.
31) Làm thế nào để sắp xếp lại thứ tự các mục trong danh sách liên kết?
Bài toán: Cho một danh sách L0 → L1 → … → Ln-1 → Ln, sắp xếp lại như sau: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
Bước sau:
- Tìm phần tử ở giữa danh sách.
- Revtrong hiệp hai.
- Ghép hai nửa lại với nhau một cách xen kẽ.
Ví dụ:
Input: 1 → 2 → 3 → 4 → 5 Output: 1 → 5 → 2 → 4 → 3
Phức tạp: O(n) thời gian, O(1) không gian.
Câu hỏi này kiểm tra nhiều thao tác trên danh sách liên kết trong cùng một câu hỏi.
32) Làm thế nào để phân vùng một danh sách liên kết dựa trên một giá trị x cho trước?
Mục tiêu:
Sắp xếp lại các nút sao cho tất cả các nút nhỏ hơn x đứng trước các nút lớn hơn hoặc bằng x.
Tiếp cận:
- Hãy duy trì hai danh sách giả:
beforevàafter. - Duyệt qua danh sách gốc và thêm các nút vào các danh sách tương ứng.
- Kết hợp chúng lại ở bước cuối cùng.
Ví dụ:
Input: 3 → 5 → 8 → 5 → 10 → 2 → 1, x = 5 Output: 3 → 2 → 1 → 5 → 8 → 5 → 10
Câu hỏi này thường được đặt ra để đánh giá khả năng sắp xếp lại dữ liệu.
33) Làm thế nào để sắp xếp một danh sách liên kết?
Vì danh sách liên kết không hỗ trợ truy cập ngẫu nhiên, Hợp nhất Sắp xếp là sự lựa chọn tốt nhất.
Bước sau:
- Chia danh sách thành hai phần bằng cách sử dụng con trỏ chậm/nhanh.
- Sắp xếp đệ quy từng nửa.
- Ghép hai nửa đã được sắp xếp lại với nhau.
Ưu điểm:
- Thời gian O(n log n).
- Không gian bổ sung O(1) (đối với phiên bản lặp).
Khác với mảng, QuickSort hoạt động kém hiệu quả đối với danh sách liên kết do độ phức tạp của việc sắp xếp lại con trỏ.
34) Sự khác biệt giữa danh sách liên kết đơn, danh sách liên kết đôi và danh sách liên kết vòng là gì?
| Tính năng | đơn lẻ | Gấp đôi | Thông tư |
|---|---|---|---|
| Liên kết | Một (tiếp theo) | Hai (trước & sau) | Nút cuối cùng kết nối với đầu. |
| Truyền tải | Chỉ chuyển tiếp | Tiến và lùi | Khả năng di chuyển vô hạn |
| Chèn/Xóa | Trung bình | Dễ dàng hơn ở cả hai đầu | Xử lý trường hợp đặc biệt |
| Trường hợp sử dụng | Ngăn xếp, Hàng đợi | Hoàn tác thao tác | Lập lịch luân phiên |
Câu hỏi so sánh này thường xuất hiện để kiểm tra sự hiểu rõ về mặt khái niệm.
35) Làm thế nào để tìm nút giao của hai danh sách liên kết vòng?
Đây là một phần mở rộng của bài toán giao điểm.
Thuật toán:
- Kiểm tra xem mỗi danh sách có chứa vòng lặp hay không.
- Nếu cả hai đều không có chu trình → hãy sử dụng thuật toán giao điểm tiêu chuẩn.
- Nếu cả hai đều là vòng lặp → hãy tìm điểm bắt đầu của vòng lặp cho mỗi vòng và kiểm tra xem chúng có giống nhau hoặc được kết nối với nhau hay không.
Vấn đề này kết hợp phát hiện chu kỳ và logic giao điểm, kiểm tra khả năng suy luận đa khái niệm.
36) Giải thích cách chèn một nút vào danh sách liên kết đã được sắp xếp.
Bước sau:
- Tạo một nút mới với giá trị đã cho.
- Di chuyển cho đến khi tìm thấy vị trí chính xác.
- Điều chỉnh
nextcác chỉ dẫn tương ứng.
Ví dụ:
Input: 1 → 3 → 5 → 7, Insert 4 Output: 1 → 3 → 4 → 5 → 7
Đây là một bài toán thao tác cơ bản để kiểm tra khả năng hiểu về việc điều chỉnh con trỏ.
37) Làm thế nào để chia một danh sách liên kết thành hai phần?
Thuật toán:
- Hãy sử dụng phương pháp con trỏ chậm và nhanh.
- Thời Gian
fastđạt đến điểm cuối,slowsẽ ở điểm giữa. - Chia tại nút đó.
Ví dụ:
Input: 1 → 2 → 3 → 4 → 5 Output: 1 → 2 → 3 and 4 → 5
Thao tác này thường là bước đầu tiên của thuật toán sắp xếp trộn danh sách liên kết.
38) Làm thế nào để tìm vị trí xuất hiện cuối cùng của một giá trị trong danh sách liên kết?
Duyệt qua danh sách đồng thời theo dõi nút cuối cùng chứa giá trị cần tìm.
Mã giả:
ListNode findLastOccurrence(ListNode head, int val) {
ListNode result = null;
while (head != null) {
if (head.val == val) result = head;
head = head.next;
}
return result;
}
Phức tạp: O (n)
Điều này giúp kiểm tra sự hiểu biết về duyệt tuyến tính và kiểm tra điều kiện.
39) Làm thế nào để xóa tất cả các lần xuất hiện của một khóa nhất định khỏi một danh sách liên kết?
Thuật toán:
- Hãy ưu tiên xử lý các nút đầu nếu chúng chứa khóa mục tiêu.
- Sau đó, duyệt qua và xóa các nút tiếp theo có chứa khóa.
Ví dụ:
Input: 1 → 2 → 6 → 3 → 4 → 5 → 6, Key = 6 Output: 1 → 2 → 3 → 4 → 5
Phức tạp: O (n)
Điều này thể hiện kiến thức về các trường hợp ngoại lệ (đặc biệt là việc xóa phần đầu).
40) Sự khác biệt chính giữa cấu trúc dữ liệu ngăn xếp và danh sách liên kết là gì?
| Tính năng | Sắp xếp | Danh sách liên kết |
|---|---|---|
| Loại truy cập | LIFO (Lượt vào cuối, Lượt ra trước) | Tuần tự |
| Triển khai hệ thống | Mảng hoặc Danh sách liên kết | Dựa trên nút |
| Operations | Đẩy/Bật | Chèn/Xóa/Duyệt |
| Linh hoạt | Giới hạn truy cập | Truy cập linh hoạt |
| Trường hợp sử dụng | Quản lý cuộc gọi hàm | Xử lý dữ liệu động |
Một ngăn xếp có thể được triển khai sử dụng danh sách liên kếtNhưng chúng khác nhau về khái niệm — ngăn xếp có quyền truy cập hạn chế trong khi danh sách liên kết là một cấu trúc đa năng.
🔍 Các câu hỏi phỏng vấn hàng đầu được liên kết chặt chẽ, kèm theo các tình huống thực tế và câu trả lời chiến lược
1) Danh sách liên kết là gì và nó khác với mảng như thế nào?
Mong đợi từ ứng viên: Người phỏng vấn muốn đánh giá sự hiểu biết của bạn về các cấu trúc dữ liệu cơ bản và khả năng so sánh các ưu nhược điểm.
Câu trả lời ví dụ: Danh sách liên kết là một cấu trúc dữ liệu tuyến tính trong đó các phần tử, được gọi là các nút, được kết nối với nhau bằng con trỏ. Mỗi nút chứa dữ liệu và một tham chiếu đến nút tiếp theo. Không giống như mảng, danh sách liên kết không yêu cầu bộ nhớ liền kề và cho phép thay đổi kích thước động, nhưng chúng có thời gian truy cập chậm hơn vì các phần tử không được đánh chỉ mục.
2) Trong một ứng dụng thực tế, khi nào bạn sẽ chọn danh sách liên kết thay vì mảng?
Mong đợi từ ứng viên: Họ đang đánh giá khả năng phán đoán thực tiễn của bạn trong việc lựa chọn cấu trúc dữ liệu phù hợp.
Câu trả lời ví dụ: Tôi sẽ chọn danh sách liên kết khi cần chèn và xóa dữ liệu thường xuyên, đặc biệt là ở giữa tập dữ liệu. Trong công việc trước đây, tôi đã làm việc trên tính năng lập lịch tác vụ, nơi các tác vụ được thêm và xóa thường xuyên, và danh sách liên kết cho hiệu suất tốt hơn so với mảng.
3) Bạn có thể giải thích sự khác biệt giữa danh sách liên kết đơn và danh sách liên kết đôi không?
Mong đợi từ ứng viên: Người phỏng vấn muốn kiểm chứng sự hiểu biết sâu sắc về mặt khái niệm và khả năng giải thích rõ ràng các khác biệt kỹ thuật của bạn.
Câu trả lời ví dụ: Danh sách liên kết đơn có các nút chỉ trỏ đến nút kế tiếp, trong khi danh sách liên kết đôi có các nút trỏ đến cả nút kế tiếp và nút trước đó. Danh sách liên kết đôi cho phép duyệt ngược dễ dàng hơn nhưng yêu cầu nhiều bộ nhớ hơn do có thêm một con trỏ.
4) Làm thế nào để phát hiện chu trình trong danh sách liên kết?
Mong đợi từ ứng viên: Bài kiểm tra này đánh giá kỹ năng giải quyết vấn đề và sự quen thuộc của bạn với các mô hình thuật toán phổ biến.
Câu trả lời ví dụ: Một phương pháp phổ biến là sử dụng hai con trỏ di chuyển với tốc độ khác nhau, thường được gọi là kỹ thuật con trỏ chậm và nhanh. Nếu có một vòng lặp, hai con trỏ cuối cùng sẽ gặp nhau. Ở một bài viết trước, tôi đã sử dụng phương pháp này để ngăn chặn các vòng lặp vô hạn trong một quy trình xử lý dữ liệu.
5) Một số thao tác phổ biến được thực hiện trên danh sách liên kết là gì?
Mong đợi từ ứng viên: Người phỏng vấn muốn xem bạn có hiểu các quy trình vận hành tiêu chuẩn và những hệ quả của chúng hay không.
Câu trả lời ví dụ: Các thao tác phổ biến bao gồm chèn, xóa, duyệt, tìm kiếm và đảo ngược danh sách. Mỗi thao tác có độ phức tạp thời gian khác nhau tùy thuộc vào vị trí thực hiện, điều này rất quan trọng khi thiết kế các hệ thống hiệu quả.
6) Làm thế nào để chèn một nút vào giữa một danh sách liên kết?
Mong đợi từ ứng viên: Họ đang kiểm tra khả năng hiểu biết về thao tác con trỏ và sự chú ý đến chi tiết của bạn.
Câu trả lời ví dụ: Để chèn một nút vào giữa, trước tiên tôi duyệt qua danh sách để tìm vị trí mục tiêu, sau đó điều chỉnh các con trỏ sao cho nút mới trỏ đến nút tiếp theo và nút trước đó trỏ đến nút mới. Việc cập nhật con trỏ cẩn thận là rất quan trọng để tránh làm hỏng danh sách.
7) Hãy mô tả một tình huống mà danh sách liên kết gây ra các vấn đề về hiệu năng và cách bạn đã giải quyết nó.
Mong đợi từ ứng viên: Câu hỏi về hành vi này đánh giá khả năng suy ngẫm và tối ưu hóa của bạn.
Câu trả lời ví dụ: Ở công ty cũ, tôi sử dụng danh sách liên kết cho các thao tác tìm kiếm thường xuyên, dẫn đến hiệu suất chậm. Tôi đã xác định được vấn đề và đề xuất chuyển sang cấu trúc dựa trên hàm băm, giúp cải thiện đáng kể thời gian tìm kiếm.
8) Làm thế nào để đảo ngược một danh sách liên kết?
Mong đợi từ ứng viên: Người phỏng vấn đang kiểm tra khả năng tư duy logic và sự hiểu biết của bạn về các phương pháp lặp hoặc đệ quy.
Câu trả lời ví dụ: Tôi sẽ đảo ngược một danh sách liên kết bằng cách lặp qua nó và thay đổi con trỏ next của mỗi nút để trỏ đến nút trước đó. Quá trình này tiếp tục cho đến khi tất cả các con trỏ được đảo ngược và phần đầu được cập nhật.
9) Việc sử dụng danh sách liên kết có những ưu điểm và nhược điểm gì?
Mong đợi từ ứng viên: Họ muốn có một góc nhìn cân bằng và nhận thức về những sự đánh đổi.
Câu trả lời ví dụ: Ưu điểm bao gồm kích thước linh hoạt và khả năng chèn và xóa hiệu quả. Nhược điểm là mức sử dụng bộ nhớ cao hơn và thời gian truy cập chậm hơn so với mảng. Trong công việc trước đây, việc hiểu rõ những sự đánh đổi này đã giúp tôi lựa chọn cấu trúc phù hợp cho các thành phần khác nhau.
10) Làm thế nào để bạn quyết định loại danh sách liên kết nào nên sử dụng trong thiết kế hệ thống?
Mong đợi từ ứng viên: Câu hỏi tình huống này đánh giá khả năng ra quyết định trong bối cảnh kiến trúc.
Câu trả lời ví dụ: Tôi xem xét các yếu tố như nhu cầu duyệt danh sách, hạn chế về bộ nhớ và tần suất hoạt động. Ví dụ, nếu cần duyệt ngược, danh sách liên kết đôi sẽ phù hợp hơn, trong khi danh sách liên kết đơn là đủ cho các triển khai đơn giản hơn và tiết kiệm bộ nhớ.
