Chương trình tìm nút giữa của danh sách liên kết đơn trong Python

Cho danh sách liên kết đơn, tìm giá trị nút giữa. Nếu có 2 nút giữa, trả về nút thứ hai. Yêu cầu một lần duyệt.

Ví dụ

Đầu vào: [5,9,6,4,8,2,1,4,5,2].
Đầu ra: 2.

Thuật toán

1. Sử dụng hai con trỏ: p (slow) và node (fast).
2. node nhảy 2 bước, p nhảy 1 bước mỗi khi node nhảy 2 bước.
3. Khi node hết, p ở giữa (hoặc nút thứ hai nếu chẵn).

Mã nguồn Python

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):
        p = node
        d = 0
        l = 0
        while node:
            if d != 2:
                node = node.next
                l += 1
                d += 1
            else:
                p = p.next
                d = 0
        return p.val if l & 1 else p.next.val

ob = Solution()
head = make_list([5,9,6,4,8,2,1,4,5,2])
print(ob.solve(head))

Đầu vào / Đầu ra

Input: [5,9,6,4,8,2,1,4,5,2]
Output: 2