資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告