꿀잠

https://leetcode.com/problems/merge-k-sorted-lists/description/

주어진 ListNode 리스트 배열의 모든 값들을 오름차순으로 변경해야한다.
값을 기준으로 오름차순으로 하면 되기 때문에 PriorityQueue 사용시 쉽게 정렬할 수 있다.
정렬한 이후에는 poll 하며 순서대로 head에 next를 연결하면 된다.

import java.util.*;  
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {  
    public ListNode mergeKLists(ListNode[] lists) {  
        PriorityQueue<ListNode> pq = new PriorityQueue<>((node1, node2) -> node2.val - node1.val);  
        for(ListNode node: lists){  
            while(node != null){  
                pq.add(node);  
                node = node.next;  
            }  
        }  
  
        ListNode head = null;  
        ListNode next = null;  
        while(!pq.isEmpty()){  
            head = pq.poll();  
            head.next = next;  
            next = head;  
        }  
  
        return head;  
    }  
}

https://leetcode.com/problems/reorder-list/description/

주어진 ListNode 의 순서를 주어진 규칙으로 재 정렬하는 문제이다. 순서대로 있던 노드를 앞,끝의 순서대로 정렬해야 한다. 이렇게 앞, 뒤에서 값을 뽑아야 할 때 쓰기 좋은 자료로 Deque가 있다. Deque는 자료 구조의 앞과 뒤에 값을 넣거나 뺄 수 있는 자료구조이다.

이를 이용하기 위해 주어진 노드를 Deque에 전부 넣은 뒤 순서대로 앞, 뒤에서 값을 빼서 연결하면 문제를 풀이할 수 있다.

/**  
 * Definition for singly-linked list. 
   * public class ListNode { 
   *     int val; 
   *     ListNode next; 
   *     ListNode() {} 
   *     ListNode(int val) { this.val = val; } 
   *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } 
   * } 
   */
   
import java.util.*;  
  
class Solution {  
    public void reorderList(ListNode head) {  
        Deque<ListNode> deque = new ArrayDeque<>();  
  
        ListNode node = head.next;  
        while(node != null){  
            deque.addLast(node);  
            node = node.next;  
        }  
  
        int i = 0;  
        while(!deque.isEmpty()){  
            ListNode next = null;  
            if(i % 2 == 0){  
                next = deque.pollLast();  
            }else{  
                next = deque.pollFirst();  
            }  
  
            head.next = next;  
            head = next;  
            i++;  
        }  
  
        head.next = null;  
    }  
  
}

ArrayList 의 contains 함수는 해당 값이 현재 List 에 있는지 확인하는 함수이다.
그런데 알고리즘 문제를 푸는 중 int[] 타입을 Arrays.asList를 이용하여 변환 후 ArrayList의 contains 함수를 이용하여 int 타입의 값이 확인이 안되는 것이었다. 확인해본 결과 contains 내부에서 값을 체크할 시 equals 함수를 사용하고 있었다.

public boolean contains(Object o) {  
    return indexOf(o) >= 0;  
}

public int indexOf(Object o) {  
    return indexOfRange(o, 0, size);  
}  

int indexOfRange(Object o, int start, int end) {  
    Object[] es = elementData;  
    if (o == null) {  
        for (int i = start; i < end; i++) {  
            if (es[i] == null) {  
                return i;  
            }  
        }    } else {  
        for (int i = start; i < end; i++) {  
            if (o.equals(es[i])) {   // 바로 이곳
                return i;  
            }  
        }    }    return -1;  
}

LinkedList 의 경우 Node 의 next 노드와 equals 함수를 이용해서 contains 상태를 확인하고 있었다. Arrays.asList 함수의 경우 int[] 타입을 변환 시킨 것이다 보니 값들이 원시타입이어서 equals 함수를 이용할 수 없어 false 가 리턴된 것으로 예상된다.

// int[] arr 일 경우
List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());

원시타입이 아닌 Integer 타입으로 위와 같이 변환하여 사용하는 것으로 해결하였다.