Giải pháp 1. Chúng ta có thể sử dụng cách tiếp cận đơn giản bằng cách duyệt qua danh sách được liên kết và đếm số phần tử sau đó chia số phần tử cho 2
Sau đó, thực hiện vòng lặp thứ hai và duyệt qua một nửa số phần tử trong danh sách được liên kết. Nhưng trong cách tiếp cận này, chúng ta phải sử dụng hai vòng lặp để lặp qua danh sách liên kết hai lần
Giải pháp 2. Chúng ta có thể tìm một giải pháp khác đó là sử dụng hai con trỏ trong danh sách liên kết. Con trỏ đầu tiên sẽ là một con trỏ chậm i. e. , di chuyển một bước cho mỗi lần lặp và con trỏ thứ hai sẽ là con trỏ nhanh di chuyển hai bước cho mỗi lần lặp
Cuối cùng, danh sách được liên kết sẽ được chia thành các phần và con trỏ nhanh sẽ ở cuối danh sách được liên kết và con trỏ chậm sẽ ở giữa danh sách được liên kết. Chúng ta có thể đạt được điều này bằng cách chỉ sử dụng một vòng lặp. Trong bài đăng này, chúng tôi sẽ tiếp cận phương pháp này để giải quyết vấn đề
Chương trình Python tìm phần tử ở giữa danh sách liên kết, cách tìm phần tử ở giữa danh sách liên kết trong python
Giới thiệu
Chúng ta có thể định nghĩa danh sách liên kết là một chuỗi các phần tử được kết nối cơ bản thông qua các liên kết. Chúng tôi có các loại hoạt động khác nhau như chèn, xóa và tìm kiếm, chúng ta hãy xem xét một trong những tìm kiếm dành cho phần tử ở giữa. Hãy cố gắng hiểu một chương trình Python cho phần tử ở giữa của danh sách được liên kết
Báo cáo sự cố về cách tìm phần tử ở giữa của danh sách được liên kết trong python
Trong bài toán này, ta được cho một danh sách liên kết đơn. Chúng ta phải tìm phần giữa của danh sách được liên kết trong một lần truyền tải
Phát biểu vấn đề Hiểu chương trình Python cho phần tử ở giữa của danh sách liên kết
Thông thường, bất cứ khi nào chúng tôi tìm thấy phần giữa của danh sách được liên kết, cần có 2 lần duyệt
- Lần duyệt đầu tiên để tìm độ dài của danh sách
- Truyền tải thứ 2 để đến nút thứ [chiều dài/2] của danh sách, đây thực sự là nút giữa của danh sách được liên kết
Nhưng ở đây chúng ta phải tìm phần giữa của danh sách liên kết trong một lần duyệt
Giả sử danh sách đã cho là 5 → 10 → 15 → 4 → 8. Giữa danh sách sẽ là 15
Đầu vào
đầu ra. 15
Giải trình. Chính giữa của danh sách đã cho là 15
Như đã nêu trong tuyên bố vấn đề, chúng ta phải tìm phần giữa của danh sách trong một lần duyệt. Làm thế nào chúng ta có thể giải quyết điều này?
- Điều gì sẽ xảy ra nếu chúng ta bắt đầu bằng cách lấy hai con trỏ, nói chậm và nhanh, và làm cho cả hai con trỏ ban đầu hướng về phía đầu
- Bây giờ, điều gì sẽ xảy ra nếu chúng ta nhảy chậm một bậc và nhảy nhanh hai bậc [di chuyển nhanh với vận tốc gấp đôi vận tốc chậm]
- Nếu chúng ta để ý kỹ, làm theo bước trên, khi nhanh sẽ đến cuối danh sách, chậm sẽ chỉ vào giữa danh sách
- Với sự trợ giúp của kỹ thuật này, chúng ta có thể đạt được nút giữa của danh sách được liên kết trong một lượt và do đó, mục tiêu tìm kiếm giữa danh sách được liên kết trong một lượt sẽ đạt được
Lý do tại sao con trỏ chậm của chúng ta sẽ trỏ đến giữa danh sách được liên kết khi con trỏ nhanh của chúng ta ở cuối là vì con trỏ chậm của chúng ta đang di chuyển với một nửa tốc độ của con trỏ nhanh nên khi con trỏ nhanh sẽ đến cuối danh sách
Bạn có biết phương pháp được giải thích ở trên được gọi là gì không?
Cách tiếp cận trên được gọi là phương pháp con trỏ chậm và nhanh. Phương pháp con trỏ chậm và nhanh đã được giải thích chi tiết trong phần tiếp cận và trong phần chạy khô
Hãy để chúng tôi có một cái nhìn thoáng qua về cách tiếp cận
Cách tiếp cận chương trình Python cho phần tử ở giữa của danh sách liên kết
Chúng ta hãy xem kỹ thuật con trỏ chậm và nhanh là gì
Ban đầu, cả con trỏ chậm và nhanh sẽ trỏ đến phần đầu của danh sách được liên kết. Sau đó, chúng tôi sẽ di chuyển cả hai con trỏ chậm và nhanh cho đến khi nhanh đến cuối. Con trỏ nhanh sẽ nhảy hai vị trí, trong khi con trỏ chậm sẽ nhảy một vị trí
Khi con trỏ nhanh sẽ đến cuối danh sách được liên kết, con trỏ chậm sẽ trỏ đến giữa danh sách được liên kết
Thuật toán tìm phần tử ở giữa danh sách liên kết trong python
- Tạo hai con trỏ chậm và nhanh
- Ban đầu, cả chậm và nhanh sẽ trỏ đến đầu danh sách
- Bây giờ, làm cho con trỏ chậm nhảy một vị trí và con trỏ nhanh nhảy hai vị trí cho đến khi nhanh đến cuối danh sách
- Khi con trỏ nhanh đến cuối danh sách, con trỏ chậm sẽ trỏ đến giữa danh sách
- Cuối cùng, trả về dữ liệu của con trỏ chậm, vì chậm sẽ trỏ đến giữa danh sách
Chương trình Dry Run for Python cho phần tử ở giữa danh sách liên kết
Triển khai mã về cách tìm phần tử ở giữa của danh sách được liên kết trong python
class Node:
def __init__[self, data]:
self.data = data
self.next = None
class LinkedList:
def __init__[self]:
self.head = None
def push[self, new_data]:
new_node = Node[new_data]
new_node.next = self.head
self.head = new_node
def printMiddle[self]:
slow_ptr = self.head
fast_ptr = self.head
if self.head is not None:
while [fast_ptr is not None and fast_ptr.next is not None]:
fast_ptr = fast_ptr.next.next
slow_ptr = slow_ptr.next
print["The middle element is: ", slow_ptr.data]
list1 = LinkedList[]
list1.push[8]
list1.push[4]
list1.push[15]
list1.push[10]
list1.push[5]
list1.printMiddle[]
đầu ra
Phần tử ở giữa là. 15
Độ phức tạp về thời gian cho chương trình Python cho phần tử ở giữa của danh sách được liên kết. O[n], vì cần duyệt qua danh sách
Trong bài viết trên, chúng tôi đã cố gắng giải thích cách tiếp cận hiệu quả nhất để tìm phần giữa của danh sách được liên kết bằng một lần duyệt đơn. Ở đây, trước tiên chúng tôi đã giải thích tuyên bố vấn đề, sau đó là các cách tiếp cận khác nhau chạy khô trong một biểu diễn bằng hình ảnh và cũng cung cấp cách triển khai mã. Nếu bạn muốn cải thiện kỹ năng của mình trên danh sách được liên kết, bạn có thể theo liên kết này Danh sách được liên kết
Bài viết liên quanDanh sách liên kết vòng kép trong cấu trúc dữ liệuỨng dụng của danh sách liên kết képỨng dụng của danh sách liên kếtDanh sách liên kết đơn vs danh sách liên kết đôiƯu nhược điểm của danh sách liên kếtDanh sách liên kết đôi tất cả các thao tác trong CBTìm kiếm nhị phân trong danh sách liên kết Sắp xếp bong bóng danh sách liên kếtXóa nút giữa của danh sách liên kếtĐa thứcCâu hỏi thường gặp về chương trình Python cho phần tử ở giữa danh sách liên kết
- Làm thế nào để bạn tìm thấy giữa một chuỗi trong python?
- slice[] làm gì trong python?
- Bạn có thể cắt một danh sách trong python không?
Với phương thức center[] tìm giữa chuỗi trong python
slice[] trả về một đối tượng có nghĩa là bạn có thể chỉ định nơi bắt đầu từ việc cắt lát và nơi kết thúc
Python hỗ trợ ký hiệu lát cho bất kỳ loại dữ liệu tuần tự nào như bộ dữ liệu, byte, mảng byte, chuỗi, danh sách và phạm vi