[Leetcode][86] Partition List

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

---

리스트노드의 head와 정수 x가 주어질 때, x보다 작은 val를 가진 노드들(let, left)은 왼쪽, x와 같거나 큰 val를 가진 노드들(let, right)은 오른쪽으로 정렬된 리스트노드의 헤드를 구하라. 이 때, left, right 그룹 내에서의 노드들은 기존 정렬 순서가 유지되어야 한다.

---

x보다 작은 val 를 가진 노드들을 저장하는 리스트 노드(left)와 x와 같거나 큰 val를 가진 노드들을 저장하는 리스트 노드(right)를 분리시킨다.

만일 left 리스트 노드가 비어있다면 right 리스트 노드의 헤드를 반환한다. left 리스트노드가 비어있지 않다면 left 리스트노드의 마지막 노드의 next에 right 리스트 노드의 head 노드를 연결시킨다.

 

시간복잡도는 O(N). N은 리스트노드의 길이.

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/86.%20Partition%20List.cpp