Palindrome Linked List

Q: Độ phức tạp thời gian của thao tác kiểm tra danh sách liên kết đối xứng là bao nhiêu?

Mỗi cách tiếp cận đều có độ phức tạp O(L) với danh sách gồm L nút, vì phải so sánh từng giá trị. Sao chép các giá trị vào một mảng hoặc đưa chúng vào ngăn xếp sẽ dùng thêm bộ nhớ O(L) ; đảo ngược nửa sau ngay tại chỗ chỉ dùng O(1) .

Q: Làm thế nào con trỏ nhanh và con trỏ chậm tìm được nút giữa của danh sách liên kết?

Cả hai đều bắt đầu ở đầu danh sách, và con trỏ nhanh đi hai bước cho mỗi bước của con trỏ chậm. Khi con trỏ nhanh đến cuối danh sách, nó đã đi hết danh sách, còn con trỏ chậm đi được một nửa.

Q: Việc đảo ngược một nửa danh sách có làm hỏng đầu vào không?

Đúng vậy, thao tác này thay đổi các liên kết của nửa sau và trong hầu hết ngôn ngữ, mảng đó thuộc về nơi gọi hàm. Nếu vẫn cần danh sách, hãy hoàn tất việc so sánh mà không trả về sớm, rồi đảo ngược nửa đó một lần nữa. Nút ở giữa vẫn liên kết với nút đầu tiên của nửa sau, nên danh sách lại nguyên vẹn mà chỉ cần thêm O(1) bộ nhớ.

DễDanh sách liên kết Con trỏ nhanh và chậm Hai con trỏ

+10

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ề true nếu các giá trị đọc từ nút đầu đến cuối giống với các giá trị đọc ngược từ cuối về đầu, nếu không thì trả về false.

Hàm

isPalindrome(next: integer-array, values: integer-array) → boolean

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ềboolean: true nếu danh sách đọc giống nhau theo cả hai chiều

Ràng buộc

1 ≤ L ≤ 5000, trong đó L là độ dài của next và values.
-100 ≤ values[i] ≤ 100
Mỗi next[i] là -1 hoặc chỉ số của một nút từ 0 đến L-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 = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
Đầu ra: true
Giải thích: Các liên kết lần lượt đi qua các nút 0, 4, 1, 3, 2, nên danh sách là 3, 1, 4, 1, 3. Hai số 3 khớp nhau, hai số 1 khớp nhau, còn số 4 ở giữa không có phần tử nào để đối chiếu.

Đầu vào: next = [2, -1, 3, 1]values = [4, 4, 9, 9]
Đầu ra: true
Giải thích: Danh sách đi qua các nút 0, 2, 3, 1 và đọc được 4, 9, 9, 4, giống nhau ở cả hai chiều.

Đầu vào: next = [2, -1, 1]values = [1, 2, 1]
Đầu ra: false
Giải thích: Mảng values là [1, 2, 1], nhưng danh sách duyệt qua các nút 0, 2, 1 và đọc được 1, 1, 2. Đọc theo thứ tự ngược lại sẽ là 2, 1, 1, nên đáp án là false.

Câu hỏi mở rộng

Bạn có thể thực hiện việc này trong thời gian O(L) với 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.

Đã mở 0/3

Lời giải

Phép kiểm tra chuỗi đối xứng ghép mỗi giá trị với giá trị đối xứng ở đầu bên kia. Danh sách liên kết đơn chỉ đi về phía trước, nên phần khó là đọc nửa sau theo thứ tự ngược lại. Bản sao mảng cần bộ nhớ O(L), trong đó L là số nút; đảo ngược các liên kết ở nửa sau chỉ cần O(1).

Sao chép các giá trị vào một mảng

Ý tưởng

Con trỏ ở đây là chỉ số nút, còn bước tiến lên là node = next[node]. Duyệt danh sách một lần và sao chép từng giá trị vào một mảng, để bạn có thể đọc từ cả hai đầu. So sánh giá trị đầu tiên và cuối cùng, di chuyển cả hai chỉ số về phía giữa, rồi trả về false nếu có bất kỳ giá trị nào không khớp. Với độ dài lẻ, giá trị ở giữa tự ghép với chính nó.

Bạn phải đọc mọi giá trị, vì vậy thời gian O(L) là tốt nhất có thể. Chi phí là L số nguyên bổ sung.

Thuật toán

Đi từ nút 0 đến -1 và thêm từng values[node] vào một mảng.
Đặt i = 0 và đặt j thành chỉ số cuối cùng.
Khi i < j, trả về false nếu hai giá trị khác nhau, nếu không thì tăng i và giảm j.
Trả về true.

def isPalindrome(next, values):
    # Write the values out in list order.
    seq = []
    node = 0
    while node != -1:
        seq.append(values[node])
        node = next[node]
    # Compare from both ends toward the middle.
    i = 0
    j = len(seq) - 1
    while i < j:
        if seq[i] != seq[j]:
            return False
        i += 1
        j -= 1
    return True

Đảo ngược nửa sau tại chỗ

Ý tưởng

Đảo ngược các liên kết của nửa sau thay vì sao chép nửa đó: đi từ nút cuối cũ sẽ dẫn về phía giữa. Để tìm điểm giữa, cho fast đi qua hai liên kết mỗi khi slow đi qua một liên kết, trong khi fast còn hai liên kết phía trước. slow dừng ở nút cuối của nửa đầu, tức nút giữa khi L là số lẻ. Trong ví dụ đầu tiên, slow đi theo đường 0 → 4 → 1 còn fast đi theo đường 0 → 1 → 2, nên slow dừng ở nút 4.

Đảo ngược các nút nằm sau slow, rồi lần lượt đi từ đầu danh sách bằng left và từ nửa đã đảo ngược bằng right: so sánh 3 với 3, rồi 1 với 1. Nửa đã đảo ngược không bao giờ dài hơn nửa đầu, nên khi dừng lúc right kết thúc, ta đã so sánh chính xác các cặp cần thiết. Mỗi giai đoạn duyệt qua tối đa L nút và lưu một vài số nguyên. Trong R, việc thay đổi next_ sẽ sao chép vector một lần, nên R dùng bộ nhớ O(L).

Thuật toán

Đặt slow = fast = 0. Khi cả next[fast] và next[next[fast]] đều không phải -1, di chuyển slow một liên kết và fast hai liên kết.
Đảo ngược danh sách bắt đầu tại next[slow]: với mỗi nút, lưu liên kết của nó, trỏ nó đến prev, sau đó di chuyển prev và nút về phía trước.
Đặt left = 0 và right = prev, nút đầu của nửa danh sách đã đảo ngược.
Khi right != -1, trả về false nếu có phần tử không khớp, nếu không thì di chuyển cả hai con trỏ một liên kết.
Trả về true.

def isPalindrome(next, values):
    # Find the middle: fast moves two links for every one link slow moves.
    slow = 0
    fast = 0
    while next[fast] != -1 and next[next[fast]] != -1:
        slow = next[slow]
        fast = next[next[fast]]
    # slow is the last node of the first half (the middle node when the length is odd).
    # Reverse the links of the second half.
    prev = -1
    node = next[slow]
    while node != -1:
        after = next[node]
        next[node] = prev
        prev = node
        node = after
    # prev is the old last node, now the head of the reversed half.
    left = 0
    right = prev
    while right != -1:
        if values[left] != values[right]:
            return False
        left = next[left]
        right = next[right]
    return True

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

Kiểm tra các mảng thay vì danh sách. Trong ví dụ thứ ba, values là [1, 2, 1], nhưng danh sách có thứ tự 1, 1, 2.
Chỉ kiểm tra next[fast] != -1. Sau đó, fast có thể nhảy đến -1 và đọc next[-1]. Trong hầu hết các ngôn ngữ, chỉ số này nằm ngoài phạm vi; trong Python và Ruby, nó âm thầm trỏ đến phần tử cuối cùng.
So sánh cho đến khi left kết thúc thay vì right. Nút ở giữa vẫn liên kết với nửa sau cũ, nên đường đi từ nút đầu dài hơn.
Ghi đè next[node] trong lúc đảo ngược trước khi lưu giá trị này, khiến phần còn lại của danh sách bị mất.
Trong Lua và R, nơi mảng bắt đầu từ chỉ số 1, đọc next[node] cho một mã nút bắt đầu từ 0. Hãy đọc next[node + 1].

Câu hỏi thường gặp3

Độ phức tạp thời gian của thao tác kiểm tra danh sách liên kết đối xứng là bao nhiêu?

Mỗi cách tiếp cận đều có độ phức tạp O(L) với danh sách gồm L nút, vì phải so sánh từng giá trị. Sao chép các giá trị vào một mảng hoặc đưa chúng vào ngăn xếp sẽ dùng thêm bộ nhớ O(L); đảo ngược nửa sau ngay tại chỗ chỉ dùng O(1).

Làm thế nào con trỏ nhanh và con trỏ chậm tìm được nút giữa của danh sách liên kết?

Cả hai đều bắt đầu ở đầu danh sách, và con trỏ nhanh đi hai bước cho mỗi bước của con trỏ chậm. Khi con trỏ nhanh đến cuối danh sách, nó đã đi hết danh sách, còn con trỏ chậm đi được một nửa.

Việc đảo ngược một nửa danh sách có làm hỏng đầu vào không?

Đúng vậy, thao tác này thay đổi các liên kết của nửa sau và trong hầu hết ngôn ngữ, mảng đó thuộc về nơi gọi hàm. Nếu vẫn cần danh sách, hãy hoàn tất việc so sánh mà không trả về sớm, rồi đảo ngược nửa đó một lần nữa. Nút ở giữa vẫn liên kết với nút đầu tiên của nửa sau, nên danh sách lại nguyên vẹn mà chỉ cần thêm O(1) bộ nhớ.

def isPalindrome(next, values):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

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

Đầu ra mong đợi

true