A-037● Day 372026.06.12mediumleetcode #143neetcode150

연결 리스트 재배치

#linked-list#two-pointers#stack#recursion

문제

· problem

P.037

연결 리스트 재배치

싱글 연결 리스트의 헤드가 주어집니다. 리스트는 다음과 같이 표현됩니다: L₀ → L₁ → … → Lₙ₋₁ → Lₙ 리스트를 다음 형태로 재배치합니다: L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → Lₙ₋₂ → … 리스트의 노드 값은 수정할 수 없습니다. 노드 자체만 변경할 수 있습니다.

제약

· 1 ≤ number of nodes ≤ 5 × 10⁴
· 1 ≤ Node.val ≤ 1000

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[1,2,3,4]

[1,4,2,3]

example 2input → output

[1,2,3,4,5]

[1,5,2,4,3]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
노드 포인터를 수정해도 되나요?
☐
리스트에 노드가 1개일 때는 어떻게 하나요?
☐
리스트가 홀수 길이일 때 중간 노드는 어떻게 되나요?
☐
추가 자료구조(스택, 큐 등)를 사용해야 하나요?
☐
리스트 중간을 어떻게 찾나요?
☐
새로운 연결 리스트 노드를 생성해야 하나요?
☐
해시맵을 사용하여 노드를 저장하는 것이 효율적인가요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 포인터 초기화

○

slow, fast = head, head.next

○

slow, fast = head, head

○

slow, fast = head.next, head

step 2· 중간 찾기│ 중첩

○

while fast and fast.next:

○

while fast:

○

while fast and fast.next and fast.next.next:

step 3· 리스트 분리

○

second = slow.next

○

second = slow

○

second = slow.next.next

step 4· 중간에서 리스트 끊기

○

prev = slow.next = None

○

prev = None

step 5· 두 번째 절반 뒤집기│ 중첩

○

while second:

○

while second.next:

step 6· 두 절반 병합│ 중첩

○

while second:

○

while first:

○

first.next = second; first = second

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

    def reorderList(self, head: ListNode) -> None:

        # find middle

        slow, fast = head, head.next

        while fast and fast.next:

            slow = slow.next

            fast = fast.next.next

        # reverse second half

        second = slow.next

        prev = slow.next = None

        while second:

            tmp = second.next

            second.next = prev

            prev = second

            second = tmp

        # merge two halfs

        first, second = head, prev

        while second:

            tmp1, tmp2 = first.next, second.next

            first.next = second

            second.next = tmp1

            first, second = tmp1, tmp2

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[1,2,3,4]

→

[1,4,2,3]

case 2

[1,2,3,4,5]

→

[1,5,2,4,3]

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.