Python 中基于值 k 排列链表节点的程序

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 不为 null 时,执行
    • 如果 cur 的值小于 k,则
      • less 的下一个 := 创建一个值与 cur 的值相同的链接列表节点
      • less := less 的下一个
    • 否则当 cur 的值大于 k 时,则
      • greater 的下一个 := 创建一个值与 cur 的值相同的链接列表节点
      • greater := greater 的下一个
    • 否则,则
      • equal 的下一个 := 创建一个值与 cur 的值相同的链接列表节点
      • equal := equal 的下一个
    • cur := cur 的下一个
  • less_head 的下一个 := equal_head 的下一个
  • equal 的下一个 := greater_head 的下一个
  • 返回 less_head 的下一个

下面是一个实现示例,以获取更好的理解−

更多Python相关文章,请阅读:Python 教程

示例

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程