리트코드 - 143. Reorder List

리트코드 - 143. Reorder List

주어진 연결리스트를 아래 규칙으로 재정렬하는 문제입니다.

정렬 전 : L(0) → L(1) → … → L(n - 1) → L(n)
정렬 후 : L(0) → L(n) → L(1) → L(n - 1) → L(2) → L(n - 2) → …

뒤에 있는 원소부터 격순으로 꺼낸다는 데 착안하여 stack을 이용했습니다. 정렬 전 순서대로 stack에 넣어주고, 하나씩 꺼내어 연결시켰습니다. for 루프가 끝나면 head는 L(n/2)에 있습니다. L(n/2 + 1)과의 연결을 끊어줍니다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
import java.util.*;

class Solution {
    public void reorderList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode back = head;
        int s;

        while (back != null) {
            stack.add(back);
            back = back.next;
        }

        s = stack.size();

        for (int i = 0; i < s / 2; i++) {
            back = stack.pop();
            back.next = head.next;
            head.next = back;
            head = back.next;
        }

        head.next = null;
    }
}