Reorder List
Bạn được cung cấp 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 và 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.
Gọi các nút theo thứ tự trong danh sách là L0, L1, ..., Lk. Sắp xếp lại danh sách theo thứ tự L0, Lk, L1, Lk-1, L2, Lk-2, ...: nút đầu tiên, rồi đến nút cuối cùng, tiếp theo là nút thứ hai, rồi đến nút gần cuối, cứ thế tiếp tục. Trả về các giá trị theo thứ tự mới đó.
Hàm
- nextinteger-array
- chỉ số của nút mà mỗi nút liên kết đến, hoặc -1 nếu là nút cuối cùng
- valuesinteger-array
- giá trị mà mỗi nút lưu giữ
- Trả vềinteger-array
- các giá trị theo thứ tự của danh sách đã sắp xếp lại
Ràng buộc
1 ≤ n ≤ 4000, trong đónlà độ dài củanextvàvalues.-1000 ≤ values[i] ≤ 1000- 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
- next = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
- Đầu ra
- [1, 5, 2, 4, 3]
- Giải thích
- Theo các liên kết từ nút
0, danh sách có các giá trị1, 2, 3, 4, 5. Giá trị đầu tiên, cuối cùng, thứ hai và áp chót lần lượt là1, 5, 2, 4, còn giá trị ở giữa3đứng cuối.
- Đầu vào
- next = [2, 3, 1, -1]values = [10, 30, 20, 40]
- Đầu ra
- [10, 40, 20, 30]
- Giải thích
- Danh sách duyệt qua các nút
0, 2, 1, 3và đọc các giá trị10, 20, 30, 40. Phần tử đầu tiên và cuối cùng cho kết quả10, 40, sau đó cặp ở giữa cho kết quả20, 30.
- Đầu vào
- next = [-1]values = [7]
- Đầu ra
- [7]
- Giải thích
- Danh sách có một nút thì không có gì để di chuyển, nên đáp án là
[7].
Câu hỏi mở rộng
Bạn có thể sắp xếp lại chính các liên kết bằng bộ nhớ bổ sung O(1) không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Viết thứ tự đích cho
1, 2, 3, 4, 5, 6. Những nút nào đến từ nửa đầu của danh sách, và các nút ở nửa sau xuất hiện theo thứ tự nào?Nửa sau xuất hiện theo thứ tự ngược:
6, 5, 4. Nếu nửa sau được đảo ngược, kết quả sẽ là hai danh sách được gộp lại bằng cách lần lượt lấy một nút từ mỗi danh sách.Tìm nút ở giữa bằng cách dùng một con trỏ chậm di chuyển một nút và một con trỏ nhanh di chuyển hai nút. Cắt danh sách sau nút giữa, đảo ngược phần thứ hai bằng cách đổi chiều các liên kết, rồi đan xen hai phần với nhau, từng nút một.
Lời giải
Thứ tự mới luân phiên giữa phần trước và phần sau, nhưng danh sách liên kết đơn chỉ duyệt theo chiều tiến. Chia công việc thành ba thao tác tiêu chuẩn trên danh sách: tìm điểm giữa bằng con trỏ chậm và con trỏ nhanh, đảo ngược nửa sau, rồi đan xen hai nửa, mỗi lần một nút.
Di chuyển phần đuôi về phía trước, từng nút một
Ý tưởng
Con trỏ ở đây là chỉ số của nút (node), còn di chuyển về phía trước là node = next[node]. Sau nút đầu tiên là nút cuối, vì vậy hãy tháo nút cuối ra rồi chèn nó sau nút hiện tại, sau đó lặp lại ở vị trí cách thêm hai nút. Với 1, 2, 3, 4, 5, ta được 1, 5, 2, 3, 4, rồi 1, 5, 2, 4, 3. Dừng lại khi có ít hơn hai nút nằm sau nút hiện tại.
Tìm nút đứng trước nút cuối đòi hỏi phải đi đến cuối danh sách ở mỗi lượt. Mỗi lượt, quãng đường đi bộ ngắn lại hai nút, tổng cộng khoảng n²/4 bước: bốn triệu bước với 4000 nút.
Thuật toán
- Đặt
cur = 0. - Khi còn ít nhất hai nút sau
cur, di chuyểnbeforetừcurcho đến khinext[next[before]] == -1, khi đótail = next[before]là nút cuối cùng. - Tháo nút này ra bằng
next[before] = -1, rồi chèn nó vào:next[tail] = next[cur]vànext[cur] = tail. - Di chuyển
curđếnnext[tail]rồi lặp lại. - Đi từ nút
0và thu thập các giá trị.
def reorderList(next, values):
cur = 0
# While at least two nodes follow cur, move the last node right after cur.
while next[cur] != -1 and next[next[cur]] != -1:
before = cur
while next[next[before]] != -1: # find the node before the tail
before = next[before]
tail = next[before]
next[before] = -1
next[tail] = next[cur]
next[cur] = tail
cur = next[tail]
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return resultSao chép các giá trị và đọc từ cả hai đầu
Ý tưởng
Mảng chạm đến phần tử cuối cùng sau một bước. Sao chép các giá trị theo thứ tự trong danh sách, [1, 2, 3, 4, 5] trong ví dụ đầu tiên, rồi đọc bằng lo từ đầu và hi từ cuối: lấy lo, lấy hi, rồi di chuyển cả hai vào trong khi lo < hi. Kết quả là 1, 5, 2, 4; với độ dài lẻ, cả hai gặp nhau tại 3 ở giữa, và phần tử này được thêm cuối cùng.
Cách này mất O(n) thời gian và O(n) bộ nhớ bổ sung, còn các liên kết không thay đổi.
Thuật toán
- Đi từ nút
0và thêm từng giá trị vàoinOrder. - Đặt
lo = 0và đặthibằng chỉ số cuối cùng. - Trong khi
lo < hi, thêminOrder[lo]vàinOrder[hi], sau đó tănglovà giảmhi. - Nếu
lo == hi, thêm giá trị ở giữa.
def reorderList(next, values):
# Write the values out in list order.
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
# Take from the front and the back in turn.
result = []
lo, hi = 0, len(in_order) - 1
while lo < hi:
result.append(in_order[lo])
result.append(in_order[hi])
lo += 1
hi -= 1
if lo == hi: # odd length: the middle value comes last
result.append(in_order[lo])
return resultTìm điểm giữa, đảo ngược nửa sau, đan xen
Ý tưởng
Với 1, 2, 3, 4, 5, 6, đáp án là 1, 6, 2, 5, 3, 4: nửa đầu 1, 2, 3 theo thứ tự, xen kẽ với nửa sau 4, 5, 6 đọc ngược. Vì vậy, hãy cắt danh sách ở giữa, đảo ngược nửa sau rồi đan xen.
slow di chuyển một liên kết trong khi fast di chuyển hai, nên slow dừng ở nút cuối cùng của nửa đầu: nút 3, dù có năm hay sáu nút. Cắt danh sách sau nút đó giúp nửa đầu có thêm một nút khi độ dài là số lẻ, và nút đó sẽ đứng cuối đáp án. Quá trình đan xen lần lượt lấy một nút từ mỗi nửa cho đến khi hết nửa sau.
Mỗi nút được chạm đến một số lần cố định, chỉ cần một vài chỉ số bộ nhớ. R sao chép vector liên kết khi có thay đổi đầu tiên, nên trong R, bộ nhớ là O(n).
Thuật toán
- Di chuyển
slowmột nút vàfasthai nút khinext[fast]vànext[next[fast]]khác-1. - Đặt
second = next[slow], sau đó đặtnext[slow] = -1. - Đảo ngược danh sách bắt đầu từ
second; đầu mới của danh sách làprev. - Đan xen: khi
secondkhác-1, nốifirstvớisecondvà nốisecondvớinext[first]trước đó, sau đó tiến cả hai lên. - Đi từ nút
0và thu thập các giá trị.
def reorderList(next, values):
# 1. Find the middle: slow stops on the last node of the first half.
slow = fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
# 2. Reverse the second half.
prev = -1
while second != -1:
after = next[second]
next[second] = prev
prev = second
second = after
# 3. Weave: one node from the front half, one from the reversed back half.
first, second = 0, prev
while second != -1:
first_after, second_after = next[first], next[second]
next[first] = second
next[second] = first_after
first, second = first_after, second_after
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return result
Lỗi thường gặp và trường hợp biên
- Không cắt danh sách (list) ở giữa. Nếu không có
next[slow] = -1, nửa đầu vẫn trỏ đến nửa sau, và sau khi đan xen, danh sách sẽ quay vòng về chính nó. - Ghi đè liên kết trước khi lưu lại. Khi đảo ngược và đan xen, trước tiên hãy đọc
next[node]vào một biến, nếu không phần còn lại của danh sách sẽ bị mất. - Đan xen cho đến khi hết nửa đầu. Với độ dài lẻ, vòng lặp đó sẽ chạy thêm một lần khi
secondlà-1và đọcnext[-1]. - Đọc thứ tự mảng (array) như thứ tự danh sách. Trong ví dụ đầu tiên,
valueslà[1, 3, 5, 2, 4], nhưng danh sách có thứ tự1, 2, 3, 4, 5. - Trong Lua và R, mảng bắt đầu từ 1. Hãy giữ chỉ số nút bắt đầu từ 0 và đọc
next[node + 1].
Câu hỏi thường gặp3
Tại sao cần đảo ngược nửa sau của danh sách?
Lời giải đọc nửa sau từ nút cuối đến nút đầu, trong khi danh sách liên kết đơn chỉ đi về phía trước. Đảo ngược nửa sau một lần, với độ phức tạp O(n), giúp quá trình trộn duyệt cả hai nửa về phía trước.
Độ phức tạp thời gian của Reorder List là bao nhiêu?
Phương thức tại chỗ chạy trong thời gian O(n) với bộ nhớ bổ sung O(1): việc tìm điểm giữa, đảo ngược và đan xen đều duyệt mỗi nút một số lần không đổi. Sao chép các giá trị vào một mảng cũng mất thời gian O(n) nhưng cần bộ nhớ O(n), còn di chuyển phần đuôi về phía trước từng nút một mất thời gian O(n²).
Vị trí ở giữa nằm ở đâu khi danh sách có số nút chẵn?
Dừng con trỏ chậm ở nút cuối cùng của nửa trước. Với sáu nút, hai nửa có ba và ba nút; với năm nút, hai nửa có ba và hai nút. Nút thừa đó sẽ nằm cuối đáp án, đúng vị trí mà thứ tự sắp xếp đặt giá trị ở giữa.
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 reorderList(next, values):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
next = [3, 4, -1, 1, 2] values = [1, 3, 5, 2, 4]
Đầu ra mong đợi
[1, 5, 2, 4, 3]