Chương trình sắp xếp các nút danh sách liên kết dựa trên giá trị k trong Python

Giả sử chúng ta có một danh sách liên kết đơn và một giá trị khác k. Chúng ta phải sắp xếp các nút sao cho tất cả các nút có giá trị nhỏ hơn k đến trước, và tất cả các nút có giá trị bằng k tiếp theo, và cuối cùng là các nút khác sau cùng. Ràng buộc là thứ tự tương đối của các nút phải được giữ nguyên.

Vì vậy, nếu đầu vào là L =[4, 3, 6, 6, 6, 10, 8] k =6, thì đầu ra sẽ là [4, 3, 6, 6, 6, 10, 8,]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• less_head:=tạo một nút danh sách được liên kết có giá trị bằng 0
• less:=less_head
• equal_head:=tạo một nút danh sách được liên kết có giá trị bằng 0
• bằng nhau:=equal_head
• great_head:=tạo một nút danh sách được liên kết có giá trị bằng 0
• lớn hơn:=great_head
• cur:=nút
• trong khi cur không phải là null, hãy thực hiện
  • nếu giá trị của cur
  • next of less:=tạo một nút danh sách được liên kết có giá trị giống với giá trị của cur
  • less:=next of less
• ngược lại khi giá trị của cur> k thì
  • tiếp theo của lớn hơn:=tạo một nút danh sách được liên kết có giá trị giống với giá trị của cur
  • lớn hơn:=tiếp theo của lớn hơn
• nếu không,
  • next of bằng:=tạo một nút danh sách được liên kết có giá trị giống với giá trị của cur
  • bằng nhau:=tiếp theo của bằng nhau
• cur:=next of cur

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, k):
   less_head = less = ListNode(0)
   equal_head = equal = ListNode(0)
   greater_head = greater = ListNode(0)
   cur = node
   while cur:
      if cur.val < k:
         less.next = ListNode(cur.val)
         less = less.next
      elif cur.val > k:
         greater.next = ListNode(cur.val)
         greater = greater.next
      else:
         equal.next = ListNode(cur.val)
         equal = equal.next
         cur = cur.next
         less.next = equal_head.next
         equal.next = greater_head.next
      return less_head.next
ob = Solution()
L = make_list([4, 3, 6, 6, 6, 10, 8])
k = 6
print_list(ob.solve(L, k))

Đầu vào

[4, 3, 6, 6, 6, 10, 8], 6

Đầu ra

[4, 3, 6, 6, 6, 10, 8, ]