Reorder List - LeetCode

Problem

1. input: 연결 리스트의 시작 노드 head
2. output: 아래의 방식으로 재정렬

• The number of nodes in the list is in the range [1, 5 * 10^4].
• 1 <= Node.val <= 1000

Idea

재정렬 규칙은 연결리스트의 중앙을 기준으로 반을 접어(역순) 하나씩 교차로 연결시키는 것이다.

1 - 2 - 3 - 4 - 5 ⇒ 1 - 5 - 2 - 4 - 3

연결리스트를 모두 큐에 넣고 머리와 꼬리에서 하나씩 뽑아 연결시켜주면 된다 → Sol1

Solution

1. Queue

   큐의 양 끝에서 하나씩 뽑아서 연결

   import java.util.*
   
   /**
    * Example:
    * var li = ListNode(5)
    * var v = li.`val`
    * Definition for singly-linked list.
    * class ListNode(var `val`: Int) {
    *     var next: ListNode? = null
    * }
    */
   class Solution {
       fun reorderList(head: ListNode?): Unit {
           val queue = LinkedList<ListNode>()
           var cursor = head
   				// 연결 리스트의 모든 노드 큐에 삽입
           while(cursor != null) {
               queue.offer(cursor)
               cursor = cursor!!.next
           }
           cursor = ListNode(0)
           while (queue.size > 1) { // 큐의 양 끝에서 하나씩 뽑아서 연결
               val left = queue.pollFirst()
               cursor!!.next = left
               val right = queue.pollLast()
               left!!.next = right
               cursor = right
               cursor!!.next = null
           }
           if (queue.size > 0) { // 노드가 홀수인 경우 처리
               val last = queue.pollLast()
               last!!.next = null
               cursor!!.next = last
           }
       }
   }
   

   시간 복잡도: 연결 리스트 순회 + 큐 순회 = n

   

Point

1. 스택이 아닌 커서를 여러개 두어, 똑같은 동작을 구현할 수도 있지만, 시간복잡도에 차이는 없음