โปรแกรมจัดเรียงโหนดรายการเชื่อมโยงตามค่า k ใน Python

สมมติว่าเรามีรายการที่เชื่อมโยงเพียงอย่างเดียวและมีค่าอื่น k เราต้องจัดเรียงโหนดเพื่อให้โหนดทั้งหมดที่มีค่าน้อยกว่า k มาก่อน และโหนดทั้งหมดที่มีค่าเท่ากับ k ถัดไป และสุดท้ายโหนดอื่นๆ ในที่สุด ข้อจำกัดคือลำดับสัมพันธ์ของโหนดควรเหมือนเดิม

ดังนั้น หากอินพุตเป็น L =[4, 3, 6, 6, 6, 10, 8] k =6 ผลลัพธ์จะเป็น [4, 3, 6, 6, 6, 10, 8, ]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• less_head :=สร้างโหนดรายการที่เชื่อมโยงโดยมีค่าเท่ากับ 0
• น้อย :=less_head
• equal_head :=สร้างโหนดรายการที่เชื่อมโยงโดยมีค่าเท่ากับ 0
• เท่ากับ :=equal_head
• greater_head :=สร้างโหนดรายการที่เชื่อมโยงโดยมีค่าเท่ากับ 0
• มากกว่า :=ใหญ่กว่า _head
• cur :=โหนด
• ในขณะที่ cur ไม่เป็นค่าว่าง ให้ทำ
  • ถ้าค่าของ cur
  • ถัดไปจากน้อยไป :=สร้างโหนดรายการที่เชื่อมโยงที่มีค่าเท่ากับค่าของ cur
  • น้อย :=ถัดไปจากน้อย
• มิฉะนั้น เมื่อค่าของ cur> k แล้ว
  • ถัดไปของค่าที่มากกว่า :=สร้างโหนดรายการที่เชื่อมโยงด้วยค่าเดียวกับค่าของ cur
  • มากกว่า :=ถัดไปจากที่มากกว่า
• มิฉะนั้น
  • next of equal :=สร้างโหนดรายการที่เชื่อมโยงโดยมีค่าเท่ากับค่าของ cur
  • เท่ากับ :=ถัดไปเท่ากับ
• cur :=ถัดไปของ cur

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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))

อินพุต

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

ผลลัพธ์

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