꿀잠

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;  
    }  
  
}

https://leetcode.com/problems/linked-list-cycle/description/

LinkedList 가 사이클을 이루며 이어져 있는지 체크하는 문제이다.
중복 체크를 위해선 가장 편한 방법 중 하나인 Set을 사용해주었다.
난이도는 특별히 높지 않았다.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;  
  
public class Solution {  
    public boolean hasCycle(ListNode head) {  
        Set<ListNode> set = new HashSet<>();  
        while(head != null){  
            if(set.contains(head)){  
                return true;  
            }  
            set.add(head);  
            head = head.next;  
        }  
  
        return false;  
    }   
}

다른 사람의 솔루션으로 속도가 좋은 방식으로는 아래와 같은 방식이 있었다. 별도의 자료구조를 사용하지 않고 두 개의 참조 값을 변화하며 비교만 하기에 속도가 뛰어났고 아이디어가 좋아 보였다.

public class Solution {
    public boolean hasCycle(ListNode head) {
        
        if(head==null||head.next==null){
            return false;
        }
        ListNode slow = head;

        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                return true;
            }
            
        }
         return false;
    }
}

두 개의 LinkedList를 정렬하여 합치는 문제이다. leetcode에서 제공하는 커스텀 클래스이며, 생성자를 잘 이용해 주어야 한다.

두 개의 리스트를 차례대로 확인하는 방법도 있겠지만 편의성을 위해 PriorityQueue를 이용하여 문제를 해결해보았다. 두 리스트의 값을 전부 넣은 이후 순서대로 꺼내서 새로 이어 주었다.

/**  
 * 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 {  
  
    PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b.compareTo(a));  
  
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {  
        ListNode answer = null;  
        pqAddAllList(list1);  
        pqAddAllList(list2);  
        while(!pq.isEmpty()){  
            answer = new ListNode(pq.poll(), answer);  
        }  
  
        return answer;  
    }  
  
    private void pqAddAllList(ListNode list){  
        while(list != null){  
            pq.add(list.val);  
            list = list.next;  
        }  
    }  
}

https://leetcode.com/problems/reverse-linked-list/description/

주어진 커스텀 클래스 형태인 Linked List 를 역순으로 생성해서 반환하는 문제이다.

/**
 * 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 reverseList(ListNode head) {
		ListNode answer = null;  
		  
		while(head != null){  
		    answer = new ListNode(head.val, answer);  
		    head = head.next;  
		}  
		  
		return answer;
    }
}

문제는 간단하게 헤드를 기준으로 새로운 노드를 만들고 순서대로 이어 붙이면 된다.
문제는 헤드부터 주어진 리스트 노드를 기준으로 새로 노드를 만들면 next에 할당하면 된다. 생성자 및 null 체크를 잘 활용해야 했다.