📕문제

[Leetcode] 143. Reorder List

문제 설명

연결 리스트의 순서를 주어진 규칙대로 재배치하는 문제다. 규칙은 다음과 같다.
[1, 2, 3, 4, 5 ... n-2, n-1, n]을 재배치하면 [1, n, 2, n-1, 3, n-2 ...]이 된다.

예를들어 [1, 2, 3, 4, 5]를 재배치하면 [1, 5, 2, 4, 3]이 된다.

---

📝풀이

deque

from collections import deque
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        deq = deque()
        cursor = head
        while cursor.next:
            deq.append(cursor.next)
            cursor = cursor.next
        cursor = head
        count = 0
        while deq:
            if count % 2 == 0:
                cursor.next = deq.pop()
            else:
                cursor.next = deq.popleft()
            cursor = cursor.next
            count += 1
        cursor.next = None

• deque를 생성해 연결 리스트의 노드들을 순서대로 집어넣는다.
• 앞에서부터, 뒤에서부터 번갈아 이어야 하므로 count를 통해 경우를 나눴다.
  • count가 짝수인 경우 deque에서 가장 끝의 요소를 꺼내고 cursor에 연결시킨다.
  • count가 홀수인 경우 deque에서 가장 앞의 요소를 꺼내고 cursor에 연결시킨다.
• 모든 연결이 끝나면 마지막 노드의 next값을 None으로 설정한다.

Runtime이 아쉬워 다른 풀이를 찾아보던 중 투포인터를 이용해 연결 리스트의 중간 노드를 찾고, 두 개의 연결 리스트로 나눈 뒤 해결하는 풀이를 발견했다.(Leetcode의 Code Sample)

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        second = slow.next
        slow.next = None
        prev = None
        while second:
            tmp = second.next
            second.next = prev
            prev = second
            second = tmp
        second = prev
        first = head

        while second:
            first_temp = first.next
            first.next = second
            second_temp = second.next
            second.next = first_temp
            second = second_temp
            first = first_temp

• 한 번에 한칸씩 이동하는 slow, 두칸씩 이동하는 fast 포인터를 사용해 중간 노드를 찾는다.
• 연결 리스트는 두개로 나뉜다. 절반 기준으로 앞의 연결 리스트 first와 뒤의 연결 리스트 second
• 연결 리스트 second를 역순으로 뒤집는다.
• first와 second의 요소를 번갈아가며 이으며 연결 리스트를 재배치한다.

Runtime이 줄었다!
deque에서 노드를 삽입/삭제하는 과정이 없어져서 그런 것 같다.