Python 中根據值 k 對連結串列節點進行排序的程式

假設我們有一個單鏈表和另一個值 k。我們需要對節點進行排序，使得所有值小於 k 的節點排在前面，所有值等於 k 的節點排在中間，最後是其他節點。約束條件是節點的相對順序應該保持不變。

因此，如果輸入類似於 L = [4, 3, 6, 6, 6, 10, 8] k = 6，則輸出將為 [4, 3, 6, 6, 6, 10, 8, ]

為了解決這個問題，我們將遵循以下步驟 -

  • less_head := 建立一個值為 0 的連結串列節點
  • less := less_head
  • equal_head := 建立一個值為 0 的連結串列節點
  • equal := equal_head
  • greater_head := 建立一個值為 0 的連結串列節點
  • greater := greater_head
  • cur := 節點
  • 當 cur 不為空時，執行以下操作
    • 如果 cur 的值 < k，則
      • less 的 next := 建立一個值為 cur 的值 的連結串列節點
      • less := less 的 next
    • 否則，當 cur 的值 > k 時，則
      • greater 的 next := 建立一個值為 cur 的值 的連結串列節點
      • greater := greater 的 next
    • 否則，
      • equal 的 next := 建立一個值為 cur 的值 的連結串列節點
      • equal := equal 的 next
    • cur := cur 的 next
  • less 的 next := equal_head 的 next
  • equal 的 next := greater_head 的 next
  • 返回 less_head 的 next

讓我們看一下以下實現以更好地理解 -

示例

 線上演示

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, ]

更新於: 2020-11-19

105 次檢視

啟動你的 職業生涯

透過完成課程獲得認證

開始
廣告