[リートコード] 0143. リストの並べ替え

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

中くらい

単一のリンクされたリストの先頭が与えられます。リストは次のように表すことができます。

L₀ →L₁ → … → Ｌ_n-1 →L_n

リストを次の形式になるように並べ替えます。

L₀ →L_n →L₁ →L_n-1 →L₂ →L_n-2 →…

リストのノードの値は変更できません。変更できるのはノード自体のみです。

例 1:

入力： 頭 = [1,2,3,4]
出力： [1,4,2,3]

例 2:

入力： 頭 = [1,2,3,4,5]
出力： [1,5,2,4,3]

制約:

リスト内のノードの数は範囲内です [1, 5 * 10 ⁴ ].
1 <= Node.val <= 1000

パイソン

				
					# 時間計算量: O(n) # 空間計算量: 入力による O(1) import オプションのクラス ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class 解決策: def reorderList(self, head: Optional[ListNode]) -> なし: head でない場合: return fast = head throw = head while fast および fast.next: fast = fast.next.next throw = throw.next prev = None curr = 遅い while curr: curr.next, prev, curr = prev, curr, curr.next first = head Second = prev while Second.next: first.next, first = Second, first.next Second.next, Second = first, Second.next return root = ListNode(1) root.next = ListNode(2) root.next.next = ListNode(3) root.next.next.next = ListNode(4) root.next.next.next.next = ListNode(5) root.next.next.next.next.next = ListNode(6) print(Solution().reorderList(root))

中くらい

パイソン

関連記事