Middle of the Linked List
Bạn có một danh sách liên kết đơn được lưu trong hai mảng có cùng độ dài. Nút i chứa giá trị values[i] và liên kết đến nút next[i], -1 đánh dấu điểm kết thúc danh sách, còn nút đầu là nút 0. Các nút không được lưu theo thứ tự trong danh sách, vì vậy hãy lần theo các liên kết.
Trả về giá trị của nút ở giữa. Khi danh sách có số nút chẵn, sẽ có hai nút ở giữa; hãy trả về giá trị của nút thứ hai.
Hàm
- valuesinteger-array
- giá trị mà mỗi nút lưu giữ
- nextinteger-array
- chỉ số của nút mà mỗi nút liên kết tới, hoặc -1 nếu là nút cuối cùng
- Trả vềinteger
- giá trị của nút ở giữa, tức nút ở giữa thứ hai khi độ dài là số chẵn
Ràng buộc
1 ≤ n ≤ 5000, trong đónlà độ dài củavaluesvànext.-104 ≤ values[i] ≤ 104- Mỗi
next[i]là-1hoặc chỉ số nút từ0đếnn-1. - Bắt đầu từ nút
0, danh sách đi qua mỗi nút đúng một lần rồi đến-1. Không có chu trình.
Ví dụ
- Đầu vào
- values = [4, 9, 2, 7, 5]next = [3, -1, 1, 4, 2]
- Đầu ra
- 5
- Giải thích
- Lần theo các liên kết từ nút
0, ta sẽ đi qua các nút0, 3, 4, 2, 1, có giá trị lần lượt là4, 7, 5, 2, 9. Nút ở giữa là nút4, có giá trị5, chứ không phải phần tử ở giữa của mảngvalues[2] = 2.
- Đầu vào
- values = [10, 20, 30, 40, 50, 60]next = [1, 2, 3, 4, 5, -1]
- Đầu ra
- 40
- Giải thích
- Ở đây, các nút được lưu theo thứ tự. Với sáu nút, có hai nút ở giữa là
30và40, và nút thứ hai được chọn.
- Đầu vào
- values = [8]next = [-1]
- Đầu ra
- 8
- Giải thích
- Danh sách có một nút thì nút đó chính là nút ở giữa.
Câu hỏi mở rộng
Bạn có thể trả về nút nằm ở vị trí một phần ba danh sách chỉ trong một lượt duyệt không? Mỗi con trỏ sẽ di chuyển nhanh đến mức nào và bạn sẽ dừng ở đâu?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Bạn không biết độ dài của danh sách cho đến khi đi đến cuối danh sách. Điều gì sẽ xảy ra nếu hai người đi bộ bắt đầu từ đầu danh sách và một người đi nhanh gấp đôi người kia?
Khi người chạy nhanh hơn đã đến cuối, người chạy chậm hơn đã đi được nửa quãng đường, nên đang ở nút giữa. Chi tiết duy nhất còn lại là thời điểm dừng để danh sách có độ dài chẵn sẽ dừng ở nút giữa thứ hai.
Bắt đầu
slowvàfasttại nút0. Khifastkhác-1vànext[fast]khác-1, di chuyểnslowmột liên kết vàfasthai liên kết. Sau đó, trả vềvalues[slow].
Lời giải
Danh sách liên kết không có chỉ số: bạn chỉ biết độ dài khi đi đến cuối danh sách, qua cả phần giữa. Bạn có thể sao chép danh sách đó vào một mảng, hoặc đếm trước rồi đi lại lần nữa. Hai con trỏ di chuyển với tốc độ khác nhau chỉ cần đi qua một lần: con trỏ chậm ở giữa danh sách khi con trỏ nhanh đi hết danh sách.
Sao chép các giá trị vào một mảng
Ý tưởng
Duyệt danh sách một lần và thêm từng giá trị vào một mảng (array): [4, 7, 5, 2, 9] trong ví dụ đầu tiên. Mảng lưu các giá trị theo thứ tự trong danh sách, nên phần tử ở giữa nằm tại chỉ số length / 2 khi chia lấy phần nguyên. Với độ dài chẵn, đó là phần tử ở giữa thứ hai: sáu giá trị cho chỉ số 3, tức là 40 trong ví dụ thứ hai. Việc duyệt tốn thời gian O(n), còn việc sao chép cần thêm O(n) bộ nhớ.
Thuật toán
- Bắt đầu với một mảng rỗng và
node = 0. - Khi
nodekhác-1, hãy thêmvalues[node]vào mảng và chuyển đếnnext[node]. - Trả về phần tử tại chỉ số
length / 2, làm tròn xuống.
def middleNode(values, next):
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
return in_order[len(in_order) // 2]Đếm rồi đi bộ nửa quãng đường
Ý tưởng
Bạn chỉ cần độ dài, không cần bản sao. Hãy đếm các nút, quay lại đầu danh sách rồi đi length / 2 bước, làm tròn xuống. Sau k bước, bạn đứng ở vị trí k, tính đầu danh sách là 0, và length / 2 là vị trí giữa: vị trí 2 trong 5 phần tử, và vị trí giữa thứ hai, vị trí 3, trong 6 phần tử. Trong ví dụ đầu tiên, bạn đếm được 5, đi theo các bước 0 → 3 → 4 rồi đọc values[4] = 5.
Bộ nhớ giảm xuống còn O(1). Đổi lại, bạn phải duyệt danh sách thêm một lần, đi tổng cộng 1.5n bước.
Thuật toán
- Đi từ nút
0đến-1và đếm số nút. - Quay lại nút
0. - Di chuyển theo
node = next[node]đúngcount / 2lần, làm tròn xuống. - Trả về
values[node].
def middleNode(values, next):
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
node = 0
for _ in range(length // 2):
node = next[node]
return values[node]Con trỏ nhanh và chậm
Ý tưởng
Mỗi vòng lặp, slow di chuyển một nút còn fast di chuyển hai nút, vì vậy sau k vòng lặp, slow ở vị trí k và fast ở vị trí 2k. Khi fast đến cuối, slow ở giữa và bạn không cần biết độ dài.
Quy tắc dừng quyết định bạn sẽ tìm được nút giữa nào. Lặp khi fast != -1 và next[fast] != -1. Với độ dài lẻ, fast dừng ở nút cuối. Với độ dài chẵn, nó đi thêm một bước đến -1, khiến slow tiến thêm một nút đến nút giữa thứ hai. Trong ví dụ thứ hai, slow đi qua các vị trí 0, 1, 2, 3 trong khi fast đi qua 0, 2, 4, -1, nên đáp án là values[3] = 40. Thuật toán chỉ cần duyệt một lượt và dùng bộ nhớ cho hai số nguyên.
Thuật toán
- Đặt
slow = 0vàfast = 0. - Trong khi
fast != -1vànext[fast] != -1, hãy đặtslow = next[slow]vàfast = next[next[fast]]. - Trả về
values[slow].
def middleNode(values, next):
slow = fast = 0
# Stop when fast is on the last node or has stepped past it.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
return values[slow]
Lỗi thường gặp và trường hợp biên
- Trả về
values[n / 2]. Các nút không được lưu theo thứ tự trong danh sách, nên ở ví dụ đầu tiên, cách này trả về2thay vì5. - Lấy phần tử giữa đầu tiên khi độ dài là số chẵn. Vòng lặp chạy khi cả
next[fast]vànext[next[fast]]đều còn hợp lệ sẽ dừng sớm một lượt và trả về30thay vì40trong ví dụ thứ hai. - Kiểm tra
next[fast]trướcfast != -1. Khi độ dài là số chẵn,fastsẽ trở thành-1, và việc đọcnext[-1]gây lỗi trong hầu hết các ngôn ngữ. Trong Python, thao tác này âm thầm đọc phần tử cuối cùng. - Đi
count / 2 - 1bước hoặc làm tròn lên trong cách đếm. Tính nút đầu là vị trí0.
Câu hỏi thường gặp3
Độ phức tạp về thời gian và không gian khi tìm phần tử giữa của danh sách liên kết là bao nhiêu?
Cả ba cách đều mất thời gian O(n), vì bạn phải duyệt ít nhất một nửa danh sách. Sao chép các giá trị cần thêm bộ nhớ O(n). Cách đếm trước và cách dùng con trỏ nhanh, con trỏ chậm đều chỉ cần O(1) bộ nhớ, còn cách dùng con trỏ chỉ cần duyệt một lần.
Làm thế nào để trả về nút ở giữa đầu tiên thay vì nút thứ hai?
Thay đổi điều kiện dừng để con trỏ nhanh dừng sớm hơn một vòng lặp: lặp khi next[fast] != -1 và next[next[fast]] != -1. Với sáu nút, con trỏ chậm sẽ dừng ở vị trí 2 thay vì 3. Trong cách tiếp cận đếm, đi (count - 1) / 2 bước thay vì count / 2.
Kỹ thuật con trỏ nhanh và chậm còn được dùng ở đâu?
Hai tốc độ này cũng phát hiện chu kỳ trong danh sách liên kết: trong vòng lặp, con trỏ nhanh vượt qua con trỏ chậm và chúng gặp nhau. Chúng cũng tìm vị trí bắt đầu chu kỳ và chia danh sách thành hai nửa để sắp xếp trộn hoặc kiểm tra xem danh sách có đọc giống nhau theo cả hai chiều hay không.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def middleNode(values, next):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
values = [4, 9, 2, 7, 5] next = [3, -1, 1, 4, 2]
Đầu ra mong đợi
5