Chương trình tìm nút cuối cùng thứ K trong danh sách liên kết trong Python

Cho danh sách liên kết đơn, tìm giá trị của nút cuối cùng thứ (0-indexed) trong một lần duyệt (single pass).

Ví dụ: , → kết quả 3 (nút index 3 từ đầu).

Giải thuật (Hai con trỏ - Two Pointers)

1. Khởi tạo , .
2. Di chuyển tiến bước.
3. Di chuyển cả và cho đến khi là .
4. Trả về .

Ví dụ minh họa

class ListNode:
    def __init__(self, data, next=None):
        self.val = data
        self.next = next

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

class Solution:
    def solve(self, node, k):
        klast = node
        last = node
        for _ in range(k):
            last = last.next
        while last.next:
            last = last.next
            klast = klast.next
        return klast.val

ob = Solution()
l1 = make_list([5, 4, 6, 3, 4, 7])
print(ob.solve(l1, 2))  # Output: 3

Đầu vào

[5,4,6,3,4,7], 2

Đầu ra

3