Reverse Linked List

Q: Độ phức tạp thời gian và không gian của việc đảo ngược danh sách liên kết là bao nhiêu?

Phiên bản lặp duyệt qua mỗi nút một lần, mất thời gian O(n) và giữ ba con trỏ, tốn thêm O(1) bộ nhớ. Sao chép thứ tự vào mảng trước cũng mất thời gian O(n) nhưng cần thêm O(n) bộ nhớ. Phiên bản đệ quy dùng O(n) bộ nhớ cho ngăn xếp lời gọi.

DễDanh sách liên kết

+10

Bạn nhận được một danh sách liên kết đơn được lưu trong mảng next: nút i 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.

Đảo ngược danh sách bằng cách đảo chiều từng liên kết, để nút cuối cũ trở thành nút đầu và nút 0 trở thành nút cuối, liên kết đến -1. Trả về mảng next đã cập nhật, có cùng độ dài với mảng đầu vào.

Hàm

reverseList(next: integer-array) → integer-array

nextinteger-array: chỉ số của nút mà mỗi nút liên kết tới, hoặc -1 đối với nút cuối cùng
Trả vềinteger-array: mảng tiếp theo của danh sách đã đảo ngược

Ràng buộc

1 ≤ next.length ≤ 5000
Mỗi next[i] là -1 hoặc chỉ số nút từ 0 đến next.length-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 = [1, 2, 3, -1]
Đầu ra: [-1, 0, 1, 2]
Giải thích: Khi đảo ngược, 0 → 1 → 2 → 3 trở thành 3 → 2 → 1 → 0: mỗi nút liên kết với nút đứng trước nó, và nút 0 liên kết với -1.

Đầu vào: next = [2, -1, 3, 1]
Đầu ra: [-1, 3, 0, 2]
Giải thích: Khi đảo ngược, 0 → 2 → 3 → 1 trở thành 1 → 3 → 2 → 0. Mỗi liên kết mới nằm ở chỉ số của nút tương ứng: [-1, 3, 0, 2], không phải mảng đảo ngược [1, 3, -1, 2].

Đầu vào: next = [-1]
Đầu ra: [-1]
Giải thích: Một nút tự đảo ngược chính nó. Nó vẫn là nút đầu và nút cuối, đồng thời vẫn liên kết với -1.

Câu hỏi mở rộng

Bạn có thể đảo ngược chỉ phần danh sách nằm giữa vị trí left và vị trí right, đồng thời giữ nguyên vị trí của các nút nằm trước và sau phần đó không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Đảo ngược danh sách không di chuyển nút nào; thao tác này chỉ đảo chiều từng liên kết. Liên kết của một nút là cách duy nhất để bạn đi đến phần còn lại của danh sách, nên khi bạn ghi đè liên kết đó, mọi thứ phía sau nó sẽ mất. Hãy ghi lại thứ tự trước, hoặc đi qua danh sách một lần và lưu lại đường đi tiếp theo trước khi đảo chiều từng liên kết.

Ghi lại thứ tự, rồi liên kết lại

Ý tưởng

Con trỏ ở đây là chỉ số nút, còn bước tiếp theo là node = next[node]. Đi từ nút 0 đến -1 và ghi lại các nút: [0, 2, 3, 1] trong ví dụ thứ hai. Trong danh sách đã đảo ngược, mỗi nút liên kết với nút đứng trước nó theo thứ tự đó, còn nút đầu cũ liên kết với -1. Ghi các liên kết đó vào một mảng mới để không ghi đè lên dữ liệu khi bạn vẫn cần dùng chúng.

Cách này cần thời gian O(n) và bộ nhớ phụ O(n) để lưu thứ tự cùng mảng mới.

Thuật toán

Đi từ nút 0 đến -1 và thêm từng nút vào order.
Tạo một mảng mới có cùng độ dài.
Đặt phần tử tại order[0] thành -1.
Với mọi k ≥ 1, đặt phần tử tại order[k] thành order[k-1].
Trả về mảng mới.

def reverseList(next):
    order = []
    node = 0
    while node != -1:
        order.append(node)
        node = next[node]
    reversed_next = [0] * len(next)
    reversed_next[order[0]] = -1  # the old head ends the new list
    for k in range(1, len(order)):
        reversed_next[order[k]] = order[k - 1]
    return reversed_next

Đảo chiều các liên kết trong một lần duyệt

Ý tưởng

Đảo chiều từng liên kết ngay khi bạn đến nút đó, đồng thời ghi nhớ nút bạn vừa đi qua trong prev. Ban đầu, prev có giá trị -1, vì nút đầu cũ sẽ trở thành nút cuối. Gán next[node] = prev sẽ xóa đường duy nhất để bạn đi tiếp, vì vậy hãy lưu đường đó vào after trước.

Tại mọi thời điểm, các nút phía sau bạn tạo thành một danh sách đảo ngược, bắt đầu từ prev, còn các nút phía trước vẫn chưa bị thay đổi, bắt đầu từ node. Khi node đạt đến -1, mọi liên kết đều đã được đảo chiều và prev là nút đầu mới. Trong ví dụ thứ hai, quá trình duyệt gán next[0] = -1, next[2] = 0, next[3] = 2 và next[1] = 3.

Mỗi nút được duyệt một lần, mất thời gian O(n) và dùng bộ nhớ cho ba số nguyên.

Thuật toán

Đặt prev = -1 và node = 0.
Khi node khác -1, lưu after = next[node].
Đặt next[node] = prev.
Tiếp tục: prev = node, rồi node = after.
Trả về next.

def reverseList(next):
    prev = -1  # the node behind the current one; the old head will point to -1
    node = 0
    while node != -1:
        after = next[node]  # save the rest of the list before cutting the link
        next[node] = prev
        prev = node
        node = after
    return next

Lỗi thường gặp và trường hợp biên

Ghi đè next[node] trước khi lưu giá trị đó. Liên kết hướng tới nút tiếp theo bị mất, và quá trình duyệt quay ngược lại thay vì tiếp tục đến nút tiếp theo.
Khởi tạo prev bằng 0 thay vì -1. Khi đó, nút 0 liên kết với chính nó.
Đảo ngược mảng thay vì các liên kết. [2, -1, 3, 1] trở thành [1, 3, -1, 2], chứ không phải [-1, 3, 0, 2].
Lặp khi next[node] != -1. Liên kết của nút cuối cùng sẽ không bao giờ được đảo chiều; hãy lặp khi node != -1.
Trong Lua và R, mảng bắt đầu từ chỉ số 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

Độ phức tạp thời gian và không gian của việc đảo ngược danh sách liên kết là bao nhiêu?

Phiên bản lặp duyệt qua mỗi nút một lần, mất thời gian O(n) và giữ ba con trỏ, tốn thêm O(1) bộ nhớ. Sao chép thứ tự vào mảng trước cũng mất thời gian O(n) nhưng cần thêm O(n) bộ nhớ. Phiên bản đệ quy dùng O(n) bộ nhớ cho ngăn xếp lời gọi.

Bạn có thể đảo ngược danh sách liên kết bằng đệ quy không?

Đúng vậy. Đảo ngược mọi thứ sau nút đầu, rồi cho nút kế tiếp cũ của nút đầu trỏ ngược về nút đầu và đặt liên kết của nút đầu thành không có gì. Cách này dễ hiểu, nhưng tạo một lời gọi lồng nhau cho mỗi nút, nên danh sách dài có thể làm tràn ngăn xếp lời gọi. Theo mặc định, Python dừng sau 1000 lời gọi, trong khi danh sách gồm 5000 nút sẽ vượt quá giới hạn đó.

Tại sao cần ba con trỏ để đảo ngược danh sách liên kết?

Để đảo chiều liên kết của một nút, bạn cần chính nút đó và nút đứng trước nó, tức là hai con trỏ. Con trỏ thứ ba giữ nút đứng sau, vì việc đảo chiều liên kết sẽ xóa tham chiếu duy nhất đến phần còn lại của danh sách. Nếu không có con trỏ này, bạn không thể tiếp tục duyệt danh sách.

def reverseList(next):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

next = [1, 2, 3, -1]

Đầu ra mong đợi

[-1, 0, 1, 2]