(Linked List, Medium) Reorder List

https://leetcode.com/problems/reorder-list/description/

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
순서대로 정렬하라는데..

중간을 찾아서 중간 뒤에서부터는 역순으로 정렬하고 머지하는 과정이 필요하겠다.
중간은 fast, slow 포인터로 O(N)으로 찾을 수 있다.

slow는 한 칸씩, fast는 두 칸씩 이동해서 없을 때까지 찾으면 최종적으로 slow 포인터는 딱 중간에 위치하게 된다.

이후 slow.next를 시작으로 뒤집으면 절반의 뒤집어진 리스트를 얻을 수 있다.
구했으면 slow.next를 명확히 null로 끊어주고,

그 다음 우리가 원하는 대로 머지를 해주면 된다.
(정방향리스트 -> 역방향리스트 -> 정방향리스트 -> 역방향리스트 ...)

class Solution {
    public void reorderList(ListNode head) {
        
        ListNode slow = head;
        ListNode fast = head;

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

        ListNode reversed = reverse(slow.next);
        slow.next = null;

        ListNode origin = head;

        while (reversed != null) {
            ListNode temp1 = origin.next;
            ListNode temp2 = reversed.next;

            origin.next = reversed;
            reversed.next = temp1;

            origin = temp1;
            reversed = temp2;
        }
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode current = head;

        while (current != null) {
            ListNode temp = current.next;
            current.next = prev;
            prev = current;
            current = temp;
        }

        return prev;
    }
}