문제 // 자료구조 // 리스트(List) // 분할 // toJava

/**
 * [분할]
 *  값 x가 주어졌을 때 x보다 작은 노드들을 x보다 크거나 같은 노드들 보다 앞에 오도록 하는 코드를 작성
 *  만약 x가 리스트에 있다면 x는 그보다 작은 원소들 보다 뒤에 나오기만 하면 된다.
 *  즉, 원소 x는 오른쪽그룹 어딘가에 존재하면 된다. 왼쪽과 오른쪽 사이에 있을 필요는 없다.
 *
 * [예제]
 * (3) > [5] > 8 > [5] > 10 > (2) > (1) [분할5]
 * 3 > 1 > 2 > 10 > 5 > 5 > 8
 *
 * [풀이]
 *  => 요청받은 분할값 뒤로 분할값보다 작은게 있으면 앞으로 보내면 된다.
 *
 * */

public class Q04 {

    class Node {
        Node next;
        int data;
    }

    /* partitionA - 두개의 리스트를 만들어 나중에 합치는 방식 */
    Node partitionA (Node node, int x) {
        Node beforeStart = null;
        Node beforeEnd = null;
        Node afterStart = null;
        Node afterEnd = null;

        while(node != null) {
            Node next = node.next;
            node.next = null;
            if(node.data < x) {
                // == 앞쪽으로 분할 ==
                if(beforeStart == null) {
                    beforeStart = node;
                    beforeEnd = beforeStart;
                } else {
                    beforeEnd.next = node;
                    beforeEnd = node;
                }
            }
            else {
                // == 뒤쪽으로 분할 ==
                if(afterStart == null) {
                    afterStart = node;
                    afterEnd = afterStart;
                } else {
                    afterEnd.next = node;
                    afterEnd = node;
                }
            }
            node = next;
        }
        if(beforeStart == null) {
            return afterStart;
        }
        beforeEnd.next = afterStart;
        return beforeStart;
    }


    /* partitionB - 피벗을 기준으로 앞뒤로 붙이는 방식 */
    static Node partitionB(Node node, int x) {
        Node head = node;
        Node tail = node;
        while(node != null) {
            Node next = node.next;
            if(node.data < x) {
                // == 앞으로 진행 ==
                node.next = head;
                head = node;
            } else {
                // == 뒤로 진행 ==
                tail.next = node;
                tail = node;
            }
            node =next;
        }
        tail.next = null;
        return head; // new head
    }

}