연결리스트 정렬

1. 우선순위 큐 사용

package com.sprint.mission;

import java.util.*;

public class Main {
  public Node solution(List<Node> input) {
    if (input == null || input.isEmpty()) {
      return null;
    }

    // 크기 순서대로 정렬 -> 우선순위큐 사용
    // priorityQueue는 heap -> heap의 삽입/삭제는 logK (내부 정렬, input의 개수)
    // N번만큼 꺼내므로 NlogK의 시간복잡도
    PriorityQueue<Node> priorityQueue = new PriorityQueue<>((a,b) -> a.getVal() - b.getVal());

    for(Node node : input) {
      if(node != null) {
        priorityQueue.add(node);
      }
    }

    Node first = new Node(0);
    Node last = first;

    while(!priorityQueue.isEmpty()) {
      Node minNode = priorityQueue.poll();
      last.setNext(minNode);
      last = minNode;
      // 최소 노드의 head 부분만 취하고 나머지는 pq에 다시 넣기
      if(minNode.getNext() != null) {
        priorityQueue.add(minNode.getNext());
      }
    }

    return first.getNext();
  }
}

class Node {
  private int val;
  private Node next;
  public Node(int val) {
    this.val = val;
  }
  public int getVal() {
    return val;
  }
  public void setNext(Node node) {
    this.next = node;
  }
  public Node getNext() {
    return next;
  }
}

• priorityQueue는 heap -> heap의 삽입/삭제는 logK (내부 정렬, input의 개수)
• 연결리스트의 크기인 N번만큼 꺼내므로 NlogK의 시간복잡도

2. Collections.sort 사용

public class Main {
  public Node solution(List<Node> input) {
    if (input == null || input.isEmpty()) {
      return null;
    }

    List<Integer> list = new ArrayList<>();

    for(Node node : input) {
      while(node != null) {
        list.add(node.getVal());
        node = node.getNext();
      }
    }
    
    Collections.sort(list);

    Node first = new Node(0);
    Node last = first;

    for(int i = 0; i < list.size(); i++) {
      Node current = new Node(list.get(i));
      last.setNext(current);
      last = current;
    }

    return first.getNext();
  }
}

class Node {
  private int val;
  private Node next;
  public Node(int val) {
    this.val = val;
  }
  public int getVal() {
    return val;
  }
  public void setNext(Node node) {
    this.next = node;
  }
  public Node getNext() {
    return next;
  }
}

• Collections.sort()는 내부적으로 Timsort를 사용하여 NlogN의 시간복잡도
• N + NlogN + N = NlogN

TreeMap 사용 - HashMap counting + 정렬과 같음

package com.sprint.mission;

import java.util.*;

public class Main {
  public Node solution(List<Node> input) {
    if (input == null || input.isEmpty()) {
      return null;
    }

    TreeMap<Integer, Integer> map = new TreeMap<>();

    for(Node node : input) {
      while(node != null) {
        map.put(node.getVal(), map.getOrDefault(node.getVal(),0) + 1);
        node = node.getNext();
      }
    }

    Node first = new Node(0);
    Node last = first;

    for(int n : map.keySet()) {
      for(int i = 0; i < map.get(n); i++) {
        Node current = new Node(n);
        last.setNext(current);
        last = current;
      }
    }
    return first.getNext();
  }
}

class Node {
  private int val;
  private Node next;
  public Node(int val) {
    this.val = val;
  }
  public int getVal() {
    return val;
  }
  public void setNext(Node node) {
    this.next = node;
  }
  public Node getNext() {
    return next;
  }
}

• TreeMap은 내부적으로 이진 탐색 트리인 레드-블랙 트리를 사용
  • 모든 연산 (삽입, 삭제, 탐색)을 O(log N) 시간에 수행
    => NlogN