Reorder List

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

Reorder List - LeetCode

 

주어진 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;  
    }  
  
}