Giả sử chúng ta có một danh sách liên kết. Chúng ta phải sắp xếp danh sách theo thứ tự tăng dần.
Vì vậy, nếu đầu vào là [5, 8, 4, 1, 5, 6, 3], thì đầu ra sẽ là [1, 3, 4, 5, 5, 6, 8,]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
- giá trị:=một danh sách mới
- head:=node
- trong khi nút không rỗng, hãy thực hiện
- chèn giá trị của nút vào cuối các giá trị
- node:=next of node
- sắp xếp các giá trị danh sách
- giá trị:=tạo một hàng đợi kết thúc kép bằng cách lấy các phần tử của giá trị
- nút:=head
- trong khi nút không rỗng, hãy thực hiện
- giá trị của nút:=phần tử bên trái của hàng đợi và xóa phần tử bên trái hàng đợi
- node:=next of node
- quay lại đầu
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Ví dụ
import collections
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):
values = []
head = node
while node:
values.append(node.val)
node = node.next
values.sort()
values = collections.deque(values)
node = head
while node:
node.val = values.popleft()
node = node.next
return head
ob = Solution()
head = make_list([5, 8, 4, 1, 5, 6, 3])
print_list(ob.solve(head)) Đầu vào
[5, 8, 4, 1, 5, 6, 3]
Đầu ra
[1, 3, 4, 5, 5, 6, 8, ]