Giả sử chúng ta có một nút danh sách liên kết đơn, chúng ta phải tìm giá trị của nút giữa. Và khi có hai nút ở giữa, thì chúng ta sẽ trả về nút thứ hai. Chúng tôi phải cố gắng giải quyết vấn đề này trong một lượt.
Vì vậy, nếu đầu vào là [5,9,6,4,8,2,1,4,5,2], thì đầu ra sẽ là 2.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau−
-
p:=nút
-
d:=0, l:=0
-
trong khi nút không rỗng, thực hiện
-
nếu d không giống với 2 thì
-
node:=next of node
-
l:=l + 1, d:=d + 1
-
-
nếu không,
-
-
p:=tiếp theo của p, d:=0
-
trả về giá trị của p khi l là số lẻ, nếu không giá trị tiếp theo của p
-
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn
Ví dụ
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
Input: [5,9,6,4,8,2,1,4,5,2]
Đầu ra
2