[DSA][Linked List] 04. Reorder List

LeetCode 143

 

04. 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.

 

 

[질문하기]

- 리스트가 길이가 1 이하일 때는 어떻게 처리하나요?

- 추가 공간 없이 in-place로 동작해야 하나요? 

 

 

[아이디어]

- Fast and Slow 포인터로 중간 노드를 찾고

- 중간 노드 이후의 연결리스트 뒤집은 후

- 앞뒤 리스트를 하나씩 합치자

 

 

[풀이 1] Linked List - Floyd detection, reverse, merge

class Solution:
    def breakDown(self, head):
        slow, fast = head, head

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        return slow
    
    def reverseList(self, head):
        prevP, curP = None, head

        while curP:
            nextP = curP.next
            curP.next = prevP
            prevP, curP = curP, nextP
        
        return prevP
    
    def mergeList(self, front, back):
        while back:
            tmp1 = front.next
            tmp2 = back.next

            front.next = back
            back.next = tmp1

            front = tmp1
            back = tmp2

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

        middle = self.breakDown(head)
        newHead = self.reverseList(middle.next)
        middle.next = None
        self.mergeList(head, newHead)

문제를 단순화하면, 앞에서부터 하나씩과 뒤에서부터 하나씩 노드를 번갈아가며 붙여서 리스트의 순서를 재조정하는 문제이다.

앞서 리스트 뒤집기, 리스트 합치기, Fast and Slow 알고리즘 세 가지 개념을 개념을 다뤄본 경험이 있기 때문에, 이를 적절히 섞어서 풀 수 있다.

예를 들어, 연결리스트가 1 → 2 → 3 → 4 → 5라고 할 때, Fast and Slow 알고리즘을 사용하여 리스트를 두 부분 1 → 2 → 3과 4 → 5로 나눈다. (중간 노드 3) 그다음, 뒤쪽 리스트인 4 → 5를 5 → 4로 뒤집는다. 마지막으로, 두 리스트를 번갈아 가며 합치면, 1 → 5 → 2 → 4 → 3이 된다.

 

STEP 1) Fast and Slow 알고리즘 사용하여 중간 노드 구하기 (breakDown)

Fast and Slow 알고리즘을 사용하면, fast 포인터가 두 칸씩 이동하는 동안 slow 포인터는 한 칸씩 이동하므로 fast 포인터가 리스트의 끝에 다다랐을 때, slow는 리스트의 중간 노드에 있게 된다. (한쪽이 N만큼 가는 동안 다른 쪽은 N/2만큼 가게 되기 때문)

노드의 개수가 홀수이냐 짝수이냐에 따라 중간이 헷갈릴 수 있는데, 홀수 길이의 리스트라면 중간은 딱 정 중앙의 노드가 되고, 짝수 길이라면 중간을 기준으로 뒤쪽 노드가 된다.

 

STEP2) 중간 노드 기준 뒤쪽 연결리스트를 뒤집기 (reverseList)

앞에서 구한 중간 노드 middle를 기준으로 middle.next부터 뒤쪽 연결리스트를 뒤집는다.

2025.06.23 - [자료구조와 알고리즘] - [DSA][Linked List] 01. Reverse Linked List

리스트 뒤집기 작업 후, middle.next를 None으로 설정하여 앞부분과 뒤부분의 연결을 끊는다.

 

STEP3) 두 리스트를 하나씩 합치기 (mergeList)

두 리스트를 하나씩 번갈아가며 연결하는 과정에서, 연결 관계를 바꾸는 방법이 헷갈릴 수 있다.

중요한 점은, 연결을 변경하기 전에 현재의 노드를 미리 저장해두어야 한다는 것이다.

예를 들어, front 리스트의 첫 번째 노드인 1 뒤에 back 리스트의 첫 번째 노드인 5를 연결하고자 할 때를 생각해 보자.

front.next = back으로 연결한다고 가정하면, front.next가 back을 가리키게 된다. 하지만 이 경우, 기존에 front.next가 가리키고 있던 노드인 2에 더 이상 접근할 수 없게 된다. 따라서, 현재 front.next가 가리키는 노드 (2)를 미리 tmp1에 저장해 두고, 그 후에 front.next = back으로 front와 back을 연결해 준다.

이제, back 리스트의 첫 번째 노드인 5 뒤에 front.next인 2를 연결해야 한다. 그런데 back의 next는 원래 4를 가리키고 있기 때문에, back.next를 변경하면 4와의 연결이 끊어지게 된다. 따라서 back.next에 연결하기 전에 back.next를 미리 tmp2에 저장해 두고, back.next = tmp1을 통해 5 뒤에 2를 연결한다.

그 후 front와 back을 각각 업데이트하여 다음 노드를 처리할 수 있도록 하고, 이 과정을 back 리스트가 끝날 때까지 반복한다.

 

⏱️ 시간복잡도

리스트의 노드를 한 번만 순회하기 때문에, 각 메서드의 시간 복잡도는 O(n)이다.

🧠 공간복잡도

추가적인 자료구조나 동적 메모리 할당을 사용하지 않고, 고정된 변수들만 사용하기 때문에 공간 복잡도는 O(1)이다.