ผสาน แบ่ง และค้นหาโหนดลำดับที่ n จากท้าย

รูปแบบสำคัญสามแบบของรายการเชื่อมโยง

การผสานรายการที่เรียงลำดับแล้วสองรายการ

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

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    curr  = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2  # attach remaining nodes
    return dummy.next

def build(arr):
    d = ListNode(); c = d
    for v in arr:
        c.next = ListNode(v); c = c.next
    return d.next

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

print(to_list(mergeTwoLists(build([1,2,4]), build([1,3,4]))))

ติดตามการผสานทีละขั้น

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

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    curr  = dummy
    step  = 0
    while l1 and l2:
        step += 1
        if l1.val <= l2.val:
            print(f'Step {step}: pick l1({l1.val})')
            curr.next = l1; l1 = l1.next
        else:
            print(f'Step {step}: pick l2({l2.val})')
            curr.next = l2; l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next

mergeTwoLists(build([1,2,4]),build([1,3,4]))

การหาจุดกึ่งกลางด้วยตัวชี้ช้า-เร็ว

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

def split_at_mid(head):
    '''Returns (first_half_head, second_half_head).'''
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next   # second half starts here
    slow.next = None  # sever the list
    return head, mid

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next

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

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

การเรียงลำดับแบบผสานบนลิงก์ลิสต์

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

def sortList(head):
    if not head or not head.next:
        return head
    # Split
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    # Recurse
    left  = sortList(head)
    right = sortList(mid)
    # Merge
    dummy = ListNode(0)
    curr  = dummy
    while left and right:
        if left.val <= right.val:
            curr.next = left;  left  = left.next
        else:
            curr.next = right; right = right.next
        curr = curr.next
    curr.next = left or right
    return dummy.next

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

print(to_list(sortList(build([4,2,1,3]))))  # [1,2,3,4]

การค้นหาโหนดลำดับที่ n จากท้าย

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

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    fast = dummy
    for _ in range(n + 1):  # advance fast n+1 steps
        fast = fast.next
    slow = dummy
    while fast:             # advance both until fast is None
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next  # remove nth node
    return dummy.next

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

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

เหตุผลที่ต้องใช้ n+1 ขั้นในการลบโหนดลำดับที่ n

# Visual: list = [1,2,3,4,5], n=2
# dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
# After n+1=3 forward steps from dummy, fast=3
# dummy(slow)  1  2  3(fast)  4  5  None
# Advance both until fast=None:
# Step 1: slow=1, fast=4
# Step 2: slow=2, fast=5
# Step 3: slow=3, fast=None
# slow is at 3, slow.next=4 (the 2nd from end) -> delete
print('slow.next (to delete): 4')
print('Result: [1, 2, 3, 5]')

จุดตัดของลิงก์ลิสต์สองรายการ

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

def getIntersectionNode(headA, headB):
    a, b = headA, headB
    while a is not b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a  # None if no intersection

# Build: A: 4->1->\  B: 5->6->1->\ both -> 8->4->5
shared = [ListNode(v) for v in [8, 4, 5]]
shared[0].next = shared[1]; shared[1].next = shared[2]
A = ListNode(4); A.next = ListNode(1); A.next.next = shared[0]
B = ListNode(5); B.next = ListNode(6); B.next.next = ListNode(1); B.next.next.next = shared[0]
print(getIntersectionNode(A, B).val)  # 8

การผสานลิสต์ที่เรียงลำดับแล้ว k รายการ (แบ่งแยกแล้วพิชิต)

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

def mergeKLists(lists):
    def merge_two(l1, l2):
        dummy = ListNode(0); curr = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1; l1 = l1.next
            else:
                curr.next = l2; l2 = l2.next
            curr = curr.next
        curr.next = l1 or l2
        return dummy.next

    if not lists: return None
    while len(lists) > 1:
        merged = []
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i+1] if i+1 < len(lists) else None
            merged.append(merge_two(l1, l2))
        lists = merged
    return lists[0]

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

lists=[build([1,4,5]),build([1,3,4]),build([2,6])]
print(to_list(mergeKLists(lists)))  # [1,1,2,3,4,4,5,6]

ลิงก์ลิสต์คี่-คู่

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

def oddEvenList(head):
    if not head:
        return head
    odd  = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next  = even.next
        odd       = odd.next
        even.next = odd.next
        even      = even.next
    odd.next = even_head
    return head

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

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

สรุปแนวคิดทั้งหมดเข้าด้วยกัน

ตรวจสอบความเข้าใจอย่างรวดเร็ว

ทบทวนบทเรียน