Algorithms

[LeetCode] 143. Reorder List 풀이 (Java)

작은별._. 2026. 2. 11. 22:58
728x90
반응형

✔️ 오늘의 리트코드 공부 기록 – Reorder List

문제 요약 (Reorder List)

단일 연결 리스트가 주어졌을 때,
L0 → L1 → L2 → … → Ln을
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …형태로 재배치하라.
값을 바꾸는 것이 아니라 노드 자체의 연결을 변경해야 한다.


문제링크: https://leetcode.com/problems/reorder-list

🤔 처음 떠올린 아이디어

문제를 보자마자 이런 생각이 들었다.

앞에서 하나, 뒤에서 하나씩 꺼내면 되지 않나?

 


예시:

1 → 2 → 3 → 4 → 5
→ 1, 5, 2, 4, 3

 

문제는 여기서 시작된다.
단일 연결 리스트는 뒤에서 접근할 수 없다.


배열이라면 left, right 포인터로 쉽게 해결되는데, 리스트는 뒤로 못 간다.

그래서 자연스럽게 이런 선택지가 떠올랐다:

  1. 스택을 써서 뒤에서 꺼내기
  2. 리스트를 reverse 해서 뒤를 앞으로 가져오기

💡 첫 번째 방법: Stack 사용

🧠 사고 과정

 

뒤에서 접근 못 한다 → 그럼 뒤에서 접근 가능하게 만들면 되지 않나?
→ 스택에 다 넣으면 마지막부터 꺼낼 수 있다.

즉,

  1. 모든 노드를 stack에 push
  2. 앞에서부터 순회하면서 stack.pop()으로 tail 연결

코드 (Java)

  • 장점: 직관적, 구현 쉽다
  • 단점: 추가 공간 사용, Linked List 패턴 문제로 보기엔 약간 아쉽다
class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;

        Stack<ListNode> stack = new Stack<>();
        ListNode curr = head;

        // 모든 노드 stack에 저장
        while (curr != null) {
            stack.push(curr);
            curr = curr.next;
        }

        curr = head;
        int size = stack.size();

        // 절반만 처리하면 됨
        for (int i = 0; i < size / 2; i++) {

            ListNode tail = stack.pop();
            ListNode next = curr.next;

            curr.next = tail;
            tail.next = next;

            curr = next;
        }

        curr.next = null; // 마지막 정리
    }
}

 

📈 시간 / 공간 복잡도

  • 시간: O(n)
  • 공간: O(n) (stack 사용)

🔥 두 번째 방법: Reverse + Merge (정석 풀이)

🧠 Reverse 아이디어는 어떻게 떠올릴까?

우리는 이렇게 만들고 싶다: 앞쪽 절반 + 뒤쪽 절반 (역순)

예시:

1 → 2 → 3 → 4 → 5

이걸 머릿속에서 이렇게 쪼갠다:
(1 → 2 → 3) + (4 → 5)


그리고 뒤쪽을 뒤집으면:
(1 → 2 → 3) + (5 → 4)

이제 두 리스트를 번갈아 merge하면 된다.


즉 이 문제는 사실:

  1. 중간 찾기
  2. 뒤쪽 reverse
  3. 교차 merge

이 3단계 문제다.

💡 핵심 깨달음

단일 연결 리스트에서:

  • 중간 찾기 → slow / fast
  • 뒤에서 접근 → reverse
  • 번갈아 연결 → merge

이건 Linked List 패턴 문제였다.


🧠 1️⃣ slow / fast 로 중간 찾기

ListNode slow = head;
ListNode fast = head;

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}


왜 가능한가?

  • fast는 2칸씩 이동
  • slow는 1칸씩 이동
  • fast가 끝에 도달하면 slow는 정확히 중간


🧠 2️⃣ 뒤쪽 reverse

여기서 reverse를 떠올리는 이유는 단 하나다.

단일 연결 리스트는 뒤로 못 간다.
그럼 뒤를 앞으로 가져오면 된다.

 

ListNode prev = null;
ListNode curr = slow.next;
slow.next = null; // 반드시 끊어야 함

while (curr != null) {
    ListNode nextTemp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nextTemp;
}

 


이제 prev가 reverse된 두 번째 리스트의 head다.

🧠 3️⃣ 교차 merge

  • first:  1 → 2 → 3
  • second: 5 → 4

번갈아 연결:

ListNode first = head;
ListNode second = prev;

while (second != null) {

    ListNode tmp1 = first.next;
    ListNode tmp2 = second.next;

    first.next = second;
    second.next = tmp1;

    first = tmp1;
    second = tmp2;
}

 

✅ 전체 코드 (Java)

class Solution {
    public void reorderList(ListNode head) {

        if (head == null || head.next == null) return;

        // 1. 중간 찾기
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. 뒤쪽 reverse
        ListNode prev = null;
        ListNode curr = slow.next;
        slow.next = null;

        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // 3. merge
        ListNode first = head;
        ListNode second = prev;

        while (second != null) {

            ListNode tmp1 = first.next;
            ListNode tmp2 = second.next;

            first.next = second;
            second.next = tmp1;

            first = tmp1;
            second = tmp2;
        }
    }
}


📈 시간 / 공간 복잡도

  • 시간: O(n)
  • 공간: O(1)

📝 이번 문제에서 얻은 깨달음

  • 단일 연결 리스트에서 “뒤에서 접근”은 항상 reverse를 떠올리자
  • slow/fast는 “중간”이 보이면 자동 반응
  • Linked List 문제는 결국 패턴 조합 문제
728x90
반응형