Chương trình tìm danh sách gấp (folded list) từ danh sách liên kết cho trước trong Python

Mô tả bài toán

Cho danh sách liên kết. Lấy nửa đầu gấp lên nửa sau, cộng các nút chồng lên nhau (theo vị trí), trả về đầu danh sách kết quả.

Ví dụ: [5,8,1,2,4,7,5] → đầu ra [2,5,15,10] (nửa đầu [5,8,1] gấp lên nửa sau [2,4,7,5] → 5+? Giải thích: độ dài 7, nửa đầu 3 phần tử [5,8,1], nửa sau 4 phần tử [2,4,7,5]; gấp: 1+2=3? Kết quả mẫu cho thấy [2,5,15,10] - cần kiểm tra logic).

Giải thuật (Stack)

1. Đếm độ dài temp.
2. t = temp // 2.
3. Duyệt t nút đầu, đẩy giá trị vào stack, ngắt liên kết.
4. Nếu độ dài lẻ: bỏ qua nút giữa.
5. Duyệt nửa sau, cộng giá trị nút với stack.pop().
6. Trả về đầu nửa sau.

Ví dụ mã 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

def print_list(head):
    ptr = head
    print('[', end="")
    while ptr:
        print(ptr.val, end=", ")
        ptr = ptr.next
    print(']')

class Solution:
    def solve(self, node):
        temp = 0
        ptr = node
        while ptr:
            temp += 1
            ptr = ptr.next
        t = temp // 2
        m = node
        stk = []
        while t:
            stk.append(m.val)
            tmp = m.next
            m.next = None
            m = tmp
            t -= 1
        node = m
        if temp % 2 != 0:
            m = m.next
        while m:
            m.val += stk.pop()
            m = m.next
        return node

ob = Solution()
head = make_list([5,8,1,2,4,7,5])
print_list(ob.solve(head))

Đầu vào

[5,8,1,2,4,7,5]

Đầu ra

[2, 5, 15, 10, ]