Duyệt một lần để tính độ dài, duyệt lần nữa đến vị trí giữa. Nếu số nút chẵn, in 2 nút giữa.
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 print_middle(ll):
curr = ll.head
length = 0
while curr:
curr = curr.next
length += 1
curr = ll.head
for _ in range((length - 1) // 2):
curr = curr.next
if curr:
if length % 2 == 0:
print(f"Hai nút giữa: {curr.data} và {curr.next.data}")
else:
print(f"Nút giữa: {curr.data}")
else:
print("Danh sách rỗng")
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)
print_middle(ll)
Kết quả
Nhập các phần tử linked list: 56 23 78 99 34 11 Hai nút giữa: 78 và 99
Giải thích
- Tính độ dài list.
- Di chuyển đến index (length-1)//2 (0-based).
- Nếu chẵn: in nút tại index đó và nút kế tiếp.
- Có thể tối ưu bằng kỹ thuật fast/slow pointer (1 lần duyệt).