LeetCodeのトピックに関する53回目の記事は、LeetCodeの問題86「パーティションリスト」です。
トピックの意味
まず問題を見てみましょう。リンクされたテーブルと整数xが与えられたとき、リンクされたテーブルの前半の結果がxより小さく、リンクされたテーブルの後半の結果がx以上となるように、xに従ってリンクされたテーブルの要素をマージすることが要求されています。
サンプルをご覧ください：
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
3によれば、連鎖表の元素を3未満のものと3以上のものに分けることができ、そのうち122が3未満、435が3以上です。その結果、122と435からなる新しい連鎖表ができ、122と435の元素の相互の順序は変わりません。
問題解決
リンクされたテーブルとその要素をどのように扱うかについて制限はないので、テーブルとそのデータを好きなように操作することができます。 最も単純な方法は、リンクされたテーブルの要素をxに基づいて2つに分割し、それらを2つの別々のリンクされたテーブルに入れ、2つのリンクされたテーブルをマージすることだと考えるのは簡単です。マージも非常に簡単で、リンクリストを結合するだけです。
連鎖したテーブルをたどり、それぞれに別の連鎖したテーブルを挿入し、最後に2つを1つに統合すれば完了です。
コードを書くのは簡単です：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
# 2つのリンクされたテーブルを作成する
left = ListNode(0)
right = ListNode(0)
# そして、2つのリンクされたテーブルをトラバースするために使用されるポインタ
ln = left
rn = right
pnt = head
while pnt is not None:
# x未満は左に挿入し、それ以外は右に挿入する
if pnt.val < x:
ln.next = ListNode(pnt.val)
ln = ln.next
else:
rn.next = ListNode(pnt.val)
rn = rn.next
pnt = pnt.next
# 左右を組み合わせる
ln.next = right.next
return left.next
これは確かに可能ですが、元の連鎖表を破棄することで余分なスペースを空けることになります。新しいリンク・テーブルを作成せずに、この問題を解決したい場合はどうすればよいでしょうか？
連鎖表を走査し、x以上の要素を見つけたら連鎖表の末尾に移動させるだけです。こうして探索が終わると、連鎖表の操作は完了です。この考え方は単純ですが、時間の実装には多くの落とし穴があり、特に注意が必要です。
例えば、トラバーサル中にいくつかの要素がチェーンテーブルの末尾に移動する可能性があるため、トラバーサルのフォーカスを記録するための値が必要です。そのため、Noneを終点として使用することはできません。x以上の最初の要素を終点として使用し、探索がこの位置に達したときに終了する必要があります。チェインテーブルの操作については、他にも多くの詳細がありますので、コードを見に来てください：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
tail = head
if head is None:
return None
# x以上の要素が端の後ろに配置されていることを見つけるとき、終わりを見つける
while tail.next is not None:
tail = tail.next
# トラバーサルの終了を記録する
end_point = None
pnt = ListNode(0)
pnt.next = head
head = pnt
while pnt.next is not end_point:
cur = pnt.next
if cur.val >= x:
# 最後に挿入する
tail.next = cur
tail = cur
# エンドポイントがNoneの場合に更新する
# end_pointそれは一度だけ更新される
if end_point is None:
end_point = cur
pnt.next = cur.next
continue
pnt = pnt.next
tail.next = None
return head.next
まとめ
この問題では、リンクされたテーブルを操作し、そこからいくつかの要素を抽出して末尾に置くことが問題です。条件を満たすために新しいリンクテーブルを作成しても、元のリンクテーブルを変更しても、アルゴリズムの複雑さは同じですが、空間の複雑さが異なるため、コーディングの複雑さも異なります。相対的に言えば、最初の方法はより単純で、2番目の方法はやや複雑ですが、連鎖表の基本的な操作に慣れていれば、決して難しいものではありません。
チェーンテーブルに関連する問題については、多くのことを行っている必要がありますが、今日のトピックは非常に基本的であると考えられている、私は我々が問題を持っている必要がないと信じて、私は繰り返しません。
