リストの分割
問題
連結リストとある値xが与えられたときにxの前にxよりも小さい値が、後にxよりも大きい値が来るようにする。
考え方
xよりも小さい数のリストと大きい数のリストを作り、最後にくっつける。
時間計算量はO(N)
コード例
import random class Node(): def __init__(self, d): self.data = d self.next = None def appendToTail(self, d): end = Node(d) n = self while n.next: n = n.next n.next = end def split(node, x): head = None mid = Node(x) end = None while node: if node.data < x: if head == None: head = Node(node.data) else: head.appendToTail(node.data) elif node.data == x: mid.appendToTail(node.data) else: if end == None: end = Node(node.data) else: end.appendToTail(node.data) node = node.next if head == None: head = mid n = head while n.next != None: n = n.next n.next = mid while n.next != None: n = n.next n.next = end return head if __name__ == "__main__": node = Node(random.randint(0, 50)) for i in range(10): node.appendToTail(random.randint(0, 50)) temp = node while temp: print(temp.data, end=" -> ") temp = temp.next node = split(node, 10) # answer print print("\n変更後") while node: print(node.data, end=" -> ") node = node.next print("")