数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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
- 如果 cur 的值 < k，则
- 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 次查看
广告