โปรแกรมหาโหนดกลางของ singly linked list ใน Python

สมมติว่ามี singly linked list node เราต้องหาค่าของโหนดกลาง ถ้ามีโหนดกลางสองตัว คืนค่าตัวที่สอง ต้องพยายามแก้ในหนึ่งรอบ (single pass)

เช่น ถ้าอินพุตคือ [5,9,6,4,8,2,1,4,5,2] ผลลัพธ์จะเป็น 2

ขั้นตอนการแก้ปัญหา

• p := node, d := 0, l := 0
• while node ไม่ใช่ null
  • ถ้า d != 2 node := node.next, l += 1, d += 1
  • มิฉะนั้น p := p.next, d := 0
• คืนค่า p.val ถ้า l เป็นคี่ มิฉะนั้น p.next.val

ตัวอย่างโค้ด

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