LeetCode #19 Remove Nth Node From End: เว้นระยะให้ pointer นำทาง

โจทย์ให้ singly linked list และ n ที่รับประกันว่าอยู่ในช่วงถูกต้อง แล้วให้ลบโหนดลำดับที่ n เมื่อนับจากท้ายครับ ความยากคือ list เดินย้อนหลังไม่ได้ เราจึงต้องแปลง “จากท้าย” ให้กลายเป็นข้อมูลที่หาได้ระหว่างเดินไปข้างหน้า

ให้นึกถึงคนสองคนเดินบนทางเส้นเดียว ถ้าคนหน้าออกก่อน n ก้าว เมื่อคนหน้าแตะปลายทาง คนหลังจะยืนก่อนจุดที่ต้องเอาออกพอดี นี่คือหัวใจของ one-pass two pointers

วิธีที่ 1: นับความยาวสองรอบ

รอบแรกนับจำนวนโหนด length รอบที่สองเดินไปยังโหนดก่อนตำแหน่ง length - n แล้วข้ามโหนดเป้าหมาย เวลา O(L), พื้นที่เพิ่ม O(1) แม้เดินสองรอบแต่เข้าใจง่ายและ debug ง่าย เหมาะเมื่อ list อ่านซ้ำได้และความชัดสำคัญกว่า latency หนึ่ง traversal

วิธีที่ 2: Two pointers หนึ่งรอบ — ค่าเริ่มต้นที่แนะนำ

ใส่ dummy ก่อนหัวเพื่อทำให้กรณีลบโหนดแรกเหมือนกรณีทั่วไป เลื่อน fast ไป n + 1 ตำแหน่งจาก dummy เพื่อรักษาช่องว่าง แล้วขยับ fast กับ slow พร้อมกันจน fast เป็น None ตอนนั้น slow.next คือโหนดเป้าหมาย เวลา O(L), พื้นที่ O(1) และเดินข้อมูลรอบเดียว

วิธีที่ 3: เก็บโหนดใน stack

เดิน list แล้วเก็บ reference ทุกโหนดรวม dummy จากนั้นหยิบโหนดก่อนเป้าหมายด้วย index จากท้าย เวลา O(L), พื้นที่ O(L) โค้ดตรงกับภาษาของโจทย์มาก แต่ไม่เหมาะเมื่อ memory จำกัด จุดเด่นคือปรับต่อได้ง่ายหากต้องแก้หลายตำแหน่งจากท้ายในคราวเดียว

import unittest


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def from_list(values):
    dummy = tail = ListNode()
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next


def to_list(node):
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result


def remove_two_pass(head, n):
    dummy = ListNode(0, head)
    length, node = 0, head
    while node:
        length += 1
        node = node.next
    before = dummy
    for _ in range(length - n):
        before = before.next
    before.next = before.next.next
    return dummy.next


def remove_two_pointers(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n + 1):
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next


def remove_stack(head, n):
    dummy = ListNode(0, head)
    stack, node = [], dummy
    while node:
        stack.append(node)
        node = node.next
    before = stack[-n - 1]
    before.next = before.next.next
    return dummy.next


class RemoveNthTests(unittest.TestCase):
    def test_methods_and_edges(self):
        cases = [
            ([1], 1, []),
            ([1, 2], 1, [1]),
            ([1, 2], 2, [2]),
            ([1, 2, 3, 4, 5], 2, [1, 2, 3, 5]),
        ]
        for values, n, expected in cases:
            for method in (remove_two_pass, remove_two_pointers, remove_stack):
                with self.subTest(method=method.__name__, values=values, n=n):
                    self.assertEqual(to_list(method(from_list(values), n)), expected)


if __name__ == "__main__":
    unittest.main()

เลือกตามสถานการณ์

เงื่อนไข	สองรอบ	Two pointers	Stack
input ใหญ่	O(L), เดินสองรอบ	O(L), เดินรอบเดียว	O(L) และเก็บทุกโหนด
memory จำกัด	O(1)	O(1)	O(L)
readability	ตรงไปตรงมา	ต้องรักษาระยะให้ถูก	ตรงกับการนับจากท้าย
sorted/streaming input	ไม่ต้อง sorted; ต้องอ่านซ้ำ	ไม่ต้อง sorted; รับ stream แบบ node chain ได้	ไม่ต้อง sorted; ต้องเก็บทั้งหมด
การแก้ input	เปลี่ยน pointer	เปลี่ยน pointer	เปลี่ยน pointer

best default ภายใต้ constraints ของโจทย์คือ two pointers เพราะผ่าน list ครั้งเดียวและใช้พื้นที่คงที่

Edge cases

dummy node สำคัญเมื่อ n == length เพราะโหนดที่ต้องลบคือหัว ทดสอบ list หนึ่งโหนด, ลบตัวท้าย, ลบตัวแรก และ list หลายโหนด โจทย์รับประกัน n ถูกต้อง; ใน production API ควรตรวจ n > 0 และไม่เกินความยาวก่อนแก้ pointer

Recap

• เว้นระยะ n + 1 จาก dummy เพื่อให้ slow หยุดก่อนเป้าหมาย
• dummy ทำให้การลบหัวไม่ต้องมี branch พิเศษ
• two pointers เป็น default ที่ได้ O(L) time และ O(1) space
• stack เหมาะเมื่อมีหลาย query จากท้ายและยอมแลก memory ได้