[LeetCode 해석 및 풀이] 143. Reorder List

LeetCode 문제 해석 및 풀이 방법

 

문제 143. Reorder List(재정렬한 리스트)

바로가기

 

문제 설명

영문

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.

 

한글

단일 연결 리스트의 head가 주어집니다. 리스트는 아래와 같이 나타내집니다

L0 → L1 → … → Ln - 1 → Ln

 

리스트를 재정렬하여 다음과 같은 형식으로 바꾸세요

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

 

리스트의 값은 바꾸지 마세요. 오직 노드 자체만 변경할 수 있습니다.

 

제한조건

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

 

입출력 예

입력	출력
head = [1,2,3,4]	[1,4,2,3]
head = [1,2,3,4,5]	[1,5,2,4,3]

 

 

해답 및 해설

파이썬 (Python)

순회를 이용한 방법

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        last_node = mid_node = head
        while last_node and last_node.next:
            mid_node = mid_node.next
            last_node = getattr(last_node.next, 'next', None)
        
        def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
            # 리스트의 순서를 뒤집음
            # 206. Reverse Linked List 해법과 같음

        dummy_head = now_node = ListNode()
        first_list = head
        second_list = reverseList(mid_node.next)
        mid_node.next = None

        while first_list and second_list:
            now_node.next = first_list
            first_list = first_list.next
            now_node.next.next = second_list
            second_list = second_list.next
            now_node = now_node.next.next

        now_node.next = first_list or second_list

206. Reverse Linked List 문제와 21. Merge Two Sorted Lists 문제를 적절하게 응용한 풀이

 

1. 두 칸씩 가는 빠른 포인터와 한 칸씩 가는 느린 포인터를 이용하여 리스트의 중간 지점을 찾는다.
2. 리스트를 둘로 쪼개 뒷쪽은 뒤집고, 앞쪽은 그대로 둔다
3. 앞쪽 리스트, 뒷쪽 리스트 순서대로 노드를 하나씩 뽑아 계속 연결해준다.

 

재귀를 이용한 풀이

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head.next or not head.next.next: return head

        pre_last_node = head
        while pre_last_node.next.next != None:
            pre_last_node = pre_last_node.next
        last_node = pre_last_node.next

        pre_last_node.next = None
        second_node = head.next
        self.reorderList(second_node)

        head.next = last_node
        last_node.next = second_node

 

 맨 처음과 맨 끝을 때어준 후, 나머지를 정렬하는 방식인데 어어엄청 느렸다.(약 9000ms) 아마 계속해서 리스트의 끝점까지 순회하는 과정이 들어가서 그런게 아닐까 싶다.