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 次查看

启动你的 职业生涯

通过完成课程获得认证

开始
广告