LeetCode: 86번 (Partition List) [JAVA]

문제 링크

https://leetcode.com/problems/partition-list/

Partition List - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 x보다 작은 노드 리스트를 위한 임시 헤더, x보다 크거나 같은 노드 리스트를 위한 임시 헤더 생성
2. 주어진 리스트, x보다 작은 노드 리스트, x보다 크거나 같은 노드 리스트를 순회하기 위한 임시 노드 초기화
3. 본래 리스트 속 노드를 while 문으로 돌며
   1) 해당 노드의 값이 x보다 작다면 x보다 작은 노드 리스트 쪽에 이어 붙임
   2) 해당 노드의 값이 x보다 크거나 같다면 x보다 크거나 같은 노드 리스트 쪽에 이어 붙임
   3) 본래 리스트 속 노드를 다음 노드로 이동
4. 이후 x보다 작은 노드 리스트 속 마지막 노드의 다음을 x보다 크거나 같은 노드 리스트 헤더의 다음 노드로 지정
5. 이후 x보다 크거나 같은 노드 리스트 속 마지막 노드의 다음 노드 값을 null로 초기화
6. x보다 작은 노드 리스트 헤더의 다음을 반환

 문제를 처음 보았을 때는 노드들의 위치를 뒤집거나 해야하는 일종의 정렬 문제처럼 느껴지지만, 이를 따로따로 분리했다가 나중에 이어붙이면 수월하게 풀 수 있는 문제이다.
 우선 주어진 x보다 작은 노드 리스트를 위한 임시 헤더, x보다 크거나 같은 노드 리스트를 위한 임시 헤더를 생성한다. 그 다음 기존 주어진 리스트를 돌면서 각 노드의 값을 비교해 서로 다른 리스트로 이어 붙일 예정이기 때문에, 주어진 리스트와 생성한 두 개의 리스트를 순회하기 위한 임시 노드를 초기화한다.
 그 다음 while문을 통해 주어진 리스트 속 노드를 도는데, 만약 해당 노드의 값이 x보다 작다면 작은 리스트 쪽에 이어 붙이고, 그 외라면 크거나 같은 값이 들어가는 리스트 쪽에 이를 이어 붙인다. 그 다음 본래 리스트 속 노드를 다음 노드로 이동하며 다음 작업을 반복한다.
 해당 작업이 끝나면 각각 따로 둔 리스트를 이어 붙이는 작업을 수행하면 되는데, 이 때 x보다 작은 노드 리스트 속 마지막 노드의 다음을 x보다 크거나 같은 노드 리스트의 임시 헤더의 다음으로 지정하면 된다. 임시 헤더는 값이 없는 텅빈 노드기 때문에 이를 건너 뛰어야 한다. 마지막으로 x보다 크거나 같은 노드 리스트의 마지막 노드의 다음을 null로 초기화하여, 해당 노드가 마지막 노드임을 표시한다. 이후 x보다 작은 리스트의 헤더 노드 다음을 반환하면 된다.

 

class Solution {
    public ListNode partition(ListNode head, int x) {
        //x보다 작은 노드들의 리스트를 위한 임시 헤더, x보다 크거나 같은 노드들의 리스트를 위한 임시 헤더 초기화
        ListNode lessThanHeadNode = new ListNode(), greaterThanOrEqualHeadNode = new ListNode();

        //주어진 리스트, x보다 작은 리스트, x보다 크거나 같은 리스트를 돌기 위한 임시 노드 초기화
        ListNode temp = head, tempLessNode = lessThanHeadNode, tempGreaterThanOrEqualNode = greaterThanOrEqualHeadNode;

        while (temp != null) {//본래 리스트 속 노드를 돌며
            if (temp.val < x) {//해당 값이 x보다 작다면 작은 리스트에 추가
                tempLessNode.next = temp;
                tempLessNode = tempLessNode.next;
            } else {//크거나 같다면 해당 리스트에 추가
                tempGreaterThanOrEqualNode.next = temp;
                tempGreaterThanOrEqualNode = tempGreaterThanOrEqualNode.next;
            }
            temp = temp.next;
        }

        tempLessNode.next = greaterThanOrEqualHeadNode.next;//x보다 작은 리스트의 끝에 크거나 같은 값들로 구성된 리스트의 시작을 추가
        tempGreaterThanOrEqualNode.next = null;//크거나 같은 값들로 구성된 리스트의 마지막을 null로 초기화

        return lessThanHeadNode.next;//임시 헤더의 다음 노드를 반환(진짜 리스트의 헤더)
    }
}

결과