Leet code (Medium): 143. Reorder List - JAVA

 

 

처음엔 Stack이나 Deque로 풀어야하나 했지만, 공간복잡도가 O(N)이 나올것이기 때문에,

좀더 효율적인 방법을 생각해야했다.

 

투 포인터를 사용하면 공간복잡도 O(1)로 문제를 해결할 수 있다.

문제의 핵심은 다음과 같다.

1. 순방향과 역방향이 둘다 존재한다.
2. 그림으로 그려보았을 때, 리스트의 앞쪽 절반은 순반향, 뒤쪽 절반은 역방향이다.

따라서, 다음과 같은 순서로 알고리즘을 진행한다.

1. 리스트의 중간 노드를 찾는다. (slow, fast 포인터를 사용. 이때, slow는 중간에 도달한다. 뒤쪽 절반의 첫 번째 노드)
2. 리스트 후반부를 역순으로 뒤집는다. (prev는 역순 리스트의 첫번째 노드. 즉, 원래 리스트의 마지막 노드)
3. 두 리스트 병합 (앞쪽 노드 next를 뒤쪽 노드로, 뒤쪽 노드 next를 앞쪽 노드로, 가리키는 노드를 안쪽으로 좁혀가며 진행)

 

/**
 * 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; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return; // 리스트가 비었거나 노드가 1개일 경우 그대로 반환
        }

        // 1. 리스트의 중간을 찾기 (slow와 fast 포인터 사용)
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // slow는 중간에 도달 (뒤쪽 절반의 첫 번째 노드)

        // 2. 리스트 후반부를 역순으로 뒤집기
        ListNode prev = null;
        ListNode curr = slow;
        while (curr != null) {
            ListNode nextTemp = curr.next; // 다음 노드를 임시 저장
            curr.next = prev; // 현재 노드를 뒤집음
            prev = curr; // prev를 현재 노드로 이동
            curr = nextTemp; // 다음 노드로 이동
        }
        
        // prev는 역순으로 뒤집힌 리스트의 첫 번째 노드 (즉, 원래 리스트의 마지막 노드)

        // 3. 두 리스트 병합
        ListNode first = head; // 첫 번째 리스트의 첫 노드
        ListNode second = prev; // 역순으로 뒤집힌 리스트의 첫 노드

        while (second.next != null) { // 뒤쪽 리스트를 기준으로 병합
            // 첫 번째 리스트의 다음 노드를 임시 저장
            ListNode temp1 = first.next;
            // 두 번째 리스트의 다음 노드를 임시 저장
            ListNode temp2 = second.next;

            // 첫 번째 리스트 노드 뒤에 두 번째 리스트 노드를 연결
            first.next = second;
            // 두 번째 리스트 노드 뒤에 첫 번째 리스트 다음 노드를 연결
            second.next = temp1;

            // 포인터를 한 칸씩 앞으로 이동
            first = temp1;
            second = temp2;
        }
    }
}