リストの分割

問題

連結リストとある値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("")