In nút thứ n từ cuối Linked List trong Python

Tính độ dài list, sau đó đi từ head (length - n) bước để đến nút thứ n từ cuối.

Ví dụ

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

class LinkedList_structure:
    def __init__(self):
        self.head = None
        self.last_node = None
    def add_vals(self, data):
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next

def list_length(ll):
    length = 0
    curr = ll.head
    while curr:
        curr = curr.next
        length += 1
    return length

def nth_from_end(ll, n):
    length = list_length(ll)
    curr = ll.head
    for _ in range(length - n):
        curr = curr.next
    return curr.data

ll = LinkedList_structure()
vals = list(map(int, input("Nhập các phần tử linked list: ").split()))
for v in vals:
    ll.add_vals(v)
n = int(input("Nhập n: "))
print(f"Phần tử thứ {n} từ cuối:", nth_from_end(ll, n))

Kết quả

Nhập các phần tử linked list: 45 31 20 87 4
Nhập n: 2
Phần tử thứ 2 từ cuối: 87

Giải thích

• Hàm list_length duyệt đếm nút.
• Hàm nth_from_end đi (length - n) bước từ head.
• Cách này cần 2 lần duyệt. Có thể tối ưu bằng 2 con trỏ (fast/slow) chỉ 1 lần duyệt.