โปรแกรมหาโหนดลำดับที่ K จากท้ายของ Linked List ใน Python

สมมติว่าเรามี singly linked list เราต้องหาค่าของโหนดลำดับที่ k จากท้าย (0-indexed) ต้องแก้ในการเดินทางครั้งเดียว (single pass)

ตัวอย่างเช่น node = [5, 4, 6, 3, 4, 7], k = 2 ผลลัพธ์คือ 3 (โหนด index 3 จากหน้า = index 2 จากท้าย)

ขั้นตอนการแก้ปัญหา (Two Pointers)

1. klast = node, last = node
2. เลื่อน last ไปข้างหน้า k ก้าว
3. วนลูป while last.next ไม่ใช่ null:
   • last = last.next
   • klast = klast.next
4. คืนค่า klast.val

ตัวอย่างโค้ด 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, k):
        klast = node
        last = node
        
        for _ in range(k):
            last = last.next
        
        while last.next:
            last = last.next
            klast = klast.next
        
        return klast.val

ob = Solution()
l1 = make_list([5, 4, 6, 3, 4, 7])
print(ob.solve(l1, 2))  # Output: 3

อินพุต

[5, 4, 6, 3, 4, 7], 2

เอาต์พุต

3