노드 정렬하기

class Node {
    int val;
    Node next;

    Node(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Practice2 {
    public static Node solution(Node[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        return divideList(lists, 0, (lists.length-1));
    }

    private static Node divideList(Node[] lists, int left, int right) {
        if(left == right){
            return lists[left];
        }


        int mid = left + (right - left) / 2;
        Node leftListNodes = divideList(lists, left , mid);
        Node RightListNodes = divideList(lists, mid + 1, right);

        return mergeNode(leftListNodes, RightListNodes);

    }

    private static Node mergeNode(Node leftListNodes, Node rightListNodes) {
        if(leftListNodes == null){
            return rightListNodes;
        }

        if(rightListNodes == null){
            return leftListNodes;
        }

        Node merge = new Node(0);
        Node currentNode = merge;

        while (leftListNodes != null && rightListNodes != null){
            if(leftListNodes.val < rightListNodes.val){
                currentNode.next = leftListNodes;
                leftListNodes = leftListNodes.next;
            }else{
                currentNode.next = rightListNodes;
                rightListNodes = rightListNodes.next;
            }

            currentNode = currentNode.next;
        }

        if(leftListNodes != null){
            currentNode.next = leftListNodes;
        }

        if(rightListNodes != null){
            currentNode.next = rightListNodes;
        }

        return merge.next;
    }


    // 문제에 주어진 2차원 배열을 링크드 리스트로 구성
    public static void setUpLinkedList(Node[] node, int[][] lists) {
        for (int i = 0; i < lists.length; i++) {
            node[i] = new Node(lists[i][0]);
        }

        for (int i = 0; i < lists.length; i++) {
            Node cur = node[i];
            for (int j = 1; j < lists[i].length; j++) {
                cur.next = new Node(lists[i][j]);
                cur = cur.next;
            }
        }
    }

    // 결과 출력 부분
    public static void printList(Node node) {
        Node cur = node;
        while (cur.next != null) {
            System.out.print(cur.val + " -> ");
            cur = cur.next;
        }
        System.out.println(cur.val);
    }

    public static void main(String[] args) {
        // Test code
        int[][] lists = {{2, 3, 9}, {1, 5, 7}, {3, 6, 7, 11}};
        Node[] node = new Node[lists.length];
        setUpLinkedList(node, lists);
        Node combinedNode = solution(node);
        printList(combinedNode);
    }
}