Giả sử chúng ta có một danh sách liên kết. Chúng ta phải lấy nửa đầu của danh sách được liên kết và gấp lại nửa sau, sau đó hợp nhất các nút giao nhau bằng cách lấy tổng của chúng. Cuối cùng, chúng ta phải trả về phần đầu kết quả của danh sách được liên kết.
Vì vậy, nếu đầu vào là [5,8,1,2,4,7,5], thì đầu ra sẽ là [2, 5, 15, 10,]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- tạm thời:=0
- ptr:=node
- trong khi ptr không null, hãy thực hiện
- temp:=temp + 1
- ptr:=tiếp theo của ptr
- t:=thương số của nhiệt độ / 2
- m:=nút
- stk:=một ngăn xếp mới
- trong khi t khác 0, hãy thực hiện
- đẩy giá trị của m vào stk
- tmp:=next of m
- tiếp theo của m:=null
- m:=tmp
- t:=t - 1
- nút:=m
- nếu nhiệt độ là chẵn thì
- m:=tiếp theo của m
- trong khi m không null, hãy thực hiện
- giá trị của m:=giá trị của m + phần tử trên cùng của ngăn xếp.
- bật ra từ stk
- m:=tiếp theo của m
- nút trả lại
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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, ]