สมมติว่าเรามีโหนดรายการที่เชื่อมโยงโดยลำพัง เราต้องหาค่าของโหนดกลาง และเมื่อมีโหนดกลางสองโหนด เราจะส่งคืนโหนดที่สอง เราต้องพยายามแก้ปัญหานี้ในครั้งเดียว
ดังนั้น หากอินพุตเป็น [5,9,6,4,8,2,1,4,5,2] เอาต์พุตจะเป็น 2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้-
-
p:=โหนด
-
d:=0, l:=0
-
ในขณะที่โหนดไม่เป็นโมฆะให้ทำ
-
ถ้า d ไม่เหมือนกับ 2 แล้ว
-
node:=ถัดไปของโหนด
-
l :=l + 1, d :=d + 1
-
-
มิฉะนั้น
-
-
p:=ถัดไปของ p, d:=0
-
คืนค่า val ของ p เมื่อ l เป็นเลขคี่ มิฉะนั้น ค่าของ next ของ p
-
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
ตัวอย่าง
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))
อินพุต
Input: [5,9,6,4,8,2,1,4,5,2]
ผลลัพธ์
2
