[Leetcode] 86. Partition List - JS

https://leetcode.com/problems/partition-list/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
연결리스트의 head와 x가 주어진다.
x보다 작은 노드는 x보다 크거나 같은 노드보다 앞에 배치하라.
단, x보다 작은 노드, x보다 크거나 같은 노드의 상대 순서는 유지하라.

제한조건
--------------------
- 연결리스트 속 노드의 갯수는 0 ~ 200이다.
- -100 <= Node.val <= 100
- -200 <= x <= 200

 

2. 접근 방법

접근방법
--------------------
x보다 작은 연결리스트 생성
x보다 크거나 같은 연결리스트 생성

head 연결리스트를 순회한다.
    - x랑 노드의 값을 비교하여 구간에 맞게 연결해준다.

x보다 작은 연결리스트 마지막 노드와 x보다 크거나 같은 연결리스트의 첫번째 노드와 연결한 연결리스트 반환

 

 

3. 코드

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var partition = function(head, x) {
    const lowerList = new ListNode(0,null);
    let lowerPrev = lowerList;
    const upperList = new ListNode(0,null);
    let upperPrev = upperList;

    while (head) {
        if (head.val < x) {
            lowerPrev = addNode(lowerPrev,head)
        } else {
            upperPrev = addNode(upperPrev,head)
        }
        head = head.next;
    }
    upperPrev.next = null // 크거나 같은 연결리스트 마지막 node.next 값 초기화 (순회 방지)
    lowerPrev.next = upperList.next // 작은 연결리스트와 크거나 같은 연결리스트 연결
    return lowerList.next;
};

function addNode(currNode,newNode) {
    currNode.next = newNode;
    return currNode.next
}

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

x보다 작은 값들을 상대적인 순서를 유지하면서 연결한 lowerList

x보다 크거나 같은 값들을 상대적인 순서를 유지하면서 연결한 upperList

 

lowerPrev, upperPrev는 순회가 종료되면 각 연결리스트의 tail(마지막 노드)를 참조한다.

순회를 방지하기 위해 upperPrev.next를 초기화한다.

lowerPrev.next를 upperList.next와 연결한다.

 

주의해야할 점은 upperList는 연결리스트 생성을 위한 dummy 이므로, upperList.next와 연결해야 정확하다.