สมมติว่ามี linked list ต้องนำครึ่งแรกมาพับทับครึ่งหลัง แล้วรวมโหนดที่ทับกันโดยบวกค่า คืน head ของลิสต์ผลลัพธ์
ตัวอย่าง: [5,8,1,2,4,7,5] ผลลัพธ์ [2,5,15,10]
ขั้นตอนการแก้ปัญหา
- นับความยาว
temp t = temp // 2, ใช้ stack เก็บค่าครึ่งแรก- เดิน
tขั้น: push ค่าเข้า stack, ตัด link, ขยับm node = m(เริ่มครึ่งหลัง)- ถ้า
tempคี่:m = m.next(ข้ามโหนดกลาง) - วนながら
mไม่ว่าง:m.val += stack.pop(),m = m.next - คืน
node
ตัวอย่างโค้ด
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))อินพุต
[5,8,1,2,4,7,5]
เอาต์พุต
[2, 5, 15, 10, ]
