คลาสโหนดและการสร้างลิสต์

รายการเชื่อมโยงคืออะไร

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

# Build: 1 -> 2 -> 3 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

# Traverse and print
curr = head
while curr:
    print(curr.val, end=' -> ')
    curr = curr.next
print('None')

การสร้างรายการจากอาร์เรย์

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

def build(arr):
    dummy = ListNode(0)
    curr = dummy
    for val in arr:
        curr.next = ListNode(val)
        curr = curr.next
    return dummy.next

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

head = build([1, 2, 3, 4, 5])
print(to_list(head))  # [1, 2, 3, 4, 5]

แทรกที่หัวและ tail

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

def insert_head(head, val):
    return ListNode(val, head)  # O(1)

def insert_tail(head, val):
    new_node = ListNode(val)
    if not head:
        return new_node
    curr = head
    while curr.next:
        curr = curr.next
    curr.next = new_node
    return head

head = None
for v in [1, 2, 3]:
    head = insert_tail(head, v)
head = insert_head(head, 0)

curr = head
while curr:
    print(curr.val, end=' -> ')
    curr = curr.next
print('None')  # 0 -> 1 -> 2 -> 3 -> None

ลบโหนดตามค่า

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

def delete_val(head, target):
    dummy = ListNode(0)
    dummy.next = head
    prev, curr = dummy, head
    while curr:
        if curr.val == target:
            prev.next = curr.next
            break
        prev, curr = curr, curr.next
    return dummy.next

def to_list(h):
    r = []
    while h:
        r.append(h.val)
        h = h.next
    return r

head = None
for v in [1, 2, 3, 2, 4]:
    dummy2 = ListNode(v)
    dummy2.next = head
    head = dummy2  # build in reverse for speed
head = delete_val(head, 2)
print(to_list(head))

ทำความเข้าใจการเปลี่ยนแปลงของตัวชี้

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

# Demonstrate safe pointer update
def swap_first_two(head):
    if not head or not head.next:
        return head
    first  = head
    second = head.next
    # Save third before losing the reference
    third  = second.next
    # Rewire
    second.next = first
    first.next  = third
    return second

from functools import reduce
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = swap_first_two(nodes[0])
curr = head
while curr:
    print(curr.val, end=' ')
    curr = curr.next
# 2 1 3 4

รายการเชื่อมโยงทางเดียวเทียบกับสองทาง

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

# Build doubly linked: 1 <-> 2 <-> 3
a, b, c = DLNode(1), DLNode(2), DLNode(3)
a.next = b; b.prev = a
b.next = c; c.prev = b

# Traverse forward
curr = a
while curr:
    print(curr.val, end=' <-> ')
    curr = curr.next
print('None')

# Traverse backward from c
curr = c
while curr:
    print(curr.val, end=' <-> ')
    curr = curr.prev
print('None')

ฟังก์ชันช่วยเหลือสำหรับความยาว tail และการพิมพ์

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

def length(head):
    count = 0
    while head:
        count += 1
        head = head.next
    return count

def tail(head):
    while head and head.next:
        head = head.next
    return head

def print_list(head):
    parts = []
    while head:
        parts.append(str(head.val))
        head = head.next
    print(' -> '.join(parts) + ' -> None')

# Build and test
nodes = [ListNode(i) for i in [10, 20, 30, 40]]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = nodes[0]
print('Length:', length(head))
print('Tail:', tail(head).val)
print_list(head)

การตั้งค่าตัวชี้สองตัวบนรายการเชื่อมโยง

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

# Find middle node using slow-fast pointers
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow   # for even length, returns second of two middle nodes

nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]

print(find_middle(nodes[0]).val)  # 3 (middle of 1->2->3->4->5)

รูปแบบโหนดหัวจำลอง

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

# Remove all nodes with val == target (may include head)
def remove_all(head, target):
    dummy = ListNode(0)
    dummy.next = head
    curr = dummy
    while curr.next:
        if curr.next.val == target:
            curr.next = curr.next.next  # skip the node
        else:
            curr = curr.next
    return dummy.next

def to_list(h):
    r = []
    while h:
        r.append(h.val)
        h = h.next
    return r

nodes = [ListNode(v) for v in [1, 2, 6, 3, 4, 5, 6]]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = remove_all(nodes[0], 6)
print(to_list(head))  # [1, 2, 3, 4, 5]

ความซับซ้อนด้านเวลาและพื้นที่

เคล็ดลับการสัมภาษณ์เรื่องรายการเชื่อมโยง

ตรวจสอบความเข้าใจ

สรุปบทเรียน