Partition List

💬 문제

[문제 링크]

연결 리스트의 첫 번째 노드 head
x 이상의 값을 가진 노드는 오른쪽으로, 나머지는 왼쪽으로 분리
순서는 유지해서 정렬된 리스트의 첫 번째 노드 반환

✍️ 나의 풀이

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function(head, x) {
    let res = new ListNode(0, head);
    let wait = res;
    let arr = [];

    while (head) {
        if (head.val < x) {
            wait.next = head;
            wait = wait.next;
        }
        else
            arr.push(head);
        head = head.next;
    }

    while (arr.length) {
        wait.next = arr.shift();
        wait = wait.next;
    }
    wait.next = null;

    return res.next;
};

head를 이동하면서 리스트를 순회
wait은 빈 노드에서부터 시작하여 정렬된 리스트를 연결해 나감
즉, head가 가리키는 노드의 값이 x보다 작으면 wait의 next로 이어서
작은 값들만 연결해 나가고 x 이상이면 arr에 넣어두고 지나감
순회가 끝나면 arr에 넣었던 노드들을 하나씩 wait에다가 이어줌
순서 유지를 위해 shift하면서 배열이 빌 때까지 진행
cycle이 생기지 않도록 마지막 노드의 next는 null로 초기화

📌 결과

Accepted
Runtime 60ms (Beats 54.97%)
Memory 51.03MB (Beats 57.83%)

📚 러닝 포인트

알고리즘은 어렵지 않게 구현했는데 역시나 이번에도 한 가지 실수를 하는 바람에 첫 제출에 에러가 났었다. 마지막 노드의 next를 초기화 시키는 것을 빼먹어서 cycle이 생성됐었다. 그 외에는 몇 번의 고뇌 끝에 잘 정리해서 구현할 수 있었다. 항상 기존 리스트의 첫 번째 노드가 반환할 리스트의 첫 번째 노드가 될 수 있는 상황 때문에 빈 노드를 만들어서 거기서부터 시작하는데, 어떻게 보면 공간만 차지하는 노드가 되므로 최대한 안 만들고 쓸 수 있는 방법을 생각해보는 것이 좋을 것 같다.