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 的下一个
- 如果 cur 的值小于 k,则
- 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, ]