Partition List
Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example 1:
Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Example 2:
Input: head = [2,1], x = 2
Output: [1,2]
Constraints:
- The number of nodes in the list is in the range
[0, 200]. -100 <= Node.val <= 100-200 <= x <= 200
アプローチ
思考
- 順序を保ちつつ、x 以上のを後ろにまとめる
- 要素を全てリストとして書き出す
- x 以上の値か、それ以下の値として分ける
- リストを merge する
- リストの値を参考に、linked list を再生成する
実装
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
greater_x_list = []
less_x_list = []
cur = head
while cur:
if cur.val >= x:
greater_x_list.append(cur.val)
else:
less_x_list.append(cur.val)
cur = cur.next
merged_list = less_x_list + greater_x_list
dummy = ListNode()
cur = dummy
for val in merged_list:
node = ListNode(val)
cur.next = node
cur = cur.next
return dummy.nextTime Space
注意点
- 管理用のリストを作り直すので、メモリ効率が悪い
- で解決できる