2.4 분할

문제 

값 x가 주어졌을때 x보다 작은 노드들을 x보다 크거나 같은 노드들 보다 앞에 오도록 하는 코드를 작성하라. 만약 x가 리스트에 있다면 x는 그보다 작은 원소들보다 뒤에 나오기만 하면 된다. 즉 원소x는 오른쪽 그룹 어딘가에 존재하기만 하면 된다. 왼쪽과 오른쪽 그룹 사이에 있을 필요는 없다. 

 

예제 

입력 : 3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1

출력 : 3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8

 

해결법

1. x보다 작은 linked list , x보다 크거나 같은 linked list 를 구성하여 마지막에 연결하기

def Solution(node):
    small_head, small_tail = None, None
    large_head, large_tail = None, None

    while node is not None:
        if node.data < k :
            if small_head is None:
                small_head , small_tail = node , node
            else :
                small_tail.next = node
                small_tail = node
        else :
            if large_head is None :
                large_head, large_tail = node, node
            else :
                large_tail.next = node
                large_tail = node
        node = node.next

    if small_head is None :
        return large_head

    small_tail.next = large_head
    return small_head

2. 변수를 더 줄여서 존재하는 노드를 이용한 새로운 리스트 구성하기 

def Solution(node):
    head, tail = node, node
    while node is not None:
        if node.data < k :
            node.next = head
            head = node
        else :
            tail.next = node
            tail = node
        node = node.next

    tail.next = None
    return head