876.チェーンテーブルの中間ノード(Python)
1632 ワード
タイトル
難易度:★☆☆☆☆タイプ:チェーンテーブル
ヘッダノードheadを有する非空の単一チェーンテーブルが与えられ、チェーンテーブルの中間ノードが返される.
中間ノードが2つある場合は、2番目の中間ノードを返します.
指定されたチェーンテーブルのノード数は1~100です.
例
例1入力:[1,2,3,4,5]出力:このリストのノード3(シーケンス化形式:[3,4,5])が返すノード値は3です.(評価システムのこのノードのシーケンス化記述は[3,4,5]である).なお、ListNodeタイプのオブジェクトansを返します.ans.val=3、ans.nextです.val = 4, ans.next.next.val=5、ans.next.next.next = NULL.
例2入力:[1,2,3,4,5,6]出力:このリストのノード4(シーケンス形式:[4,5,6])このリストには2つの中間ノードがあり、値はそれぞれ3と4であるため、2番目のノードを返します.
に答える
シナリオ1:統計長
チェーンテーブルの長さを統計し、再び遍歴して、長さの半分のノードを取り出すことができます.
シナリオ2:スナップ・スロー・ポインタ
スナップポインタを定義し、同時に最初のノードから後ろに遍歴し、スナップポインタは2ステップずつ、スローポインタは1ステップずつ歩き、スナップポインタが最後のノードまで歩いたとき、スローポインタはちょうど中間ノードまで歩いた.
質問やアドバイスがあれば、コメントエリアへようこそ~
難易度:★☆☆☆☆タイプ:チェーンテーブル
ヘッダノードheadを有する非空の単一チェーンテーブルが与えられ、チェーンテーブルの中間ノードが返される.
中間ノードが2つある場合は、2番目の中間ノードを返します.
指定されたチェーンテーブルのノード数は1~100です.
例
例1入力:[1,2,3,4,5]出力:このリストのノード3(シーケンス化形式:[3,4,5])が返すノード値は3です.(評価システムのこのノードのシーケンス化記述は[3,4,5]である).なお、ListNodeタイプのオブジェクトansを返します.ans.val=3、ans.nextです.val = 4, ans.next.next.val=5、ans.next.next.next = NULL.
例2入力:[1,2,3,4,5,6]出力:このリストのノード4(シーケンス形式:[4,5,6])このリストには2つの中間ノードがあり、値はそれぞれ3と4であるため、2番目のノードを返します.
に答える
シナリオ1:統計長
チェーンテーブルの長さを統計し、再び遍歴して、長さの半分のノードを取り出すことができます.
class Solution:
def middleNode(self, head):
"""
:param head: ListNode
:return: ListNode
"""
def get_len(node):
tmp = node
count = 0
while tmp:
count += 1
tmp = tmp.next
return count
def get_node(node, idx):
tmp = node
count = 0
while count < idx:
count += 1
tmp = tmp.next
return tmp
return get_node(head, get_len(head)//2)
シナリオ2:スナップ・スロー・ポインタ
スナップポインタを定義し、同時に最初のノードから後ろに遍歴し、スナップポインタは2ステップずつ、スローポインタは1ステップずつ歩き、スナップポインタが最後のノードまで歩いたとき、スローポインタはちょうど中間ノードまで歩いた.
class Solution:
def middleNode(self, head):
"""
:param head: ListNode
:return: ListNode
"""
fast = slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow
質問やアドバイスがあれば、コメントエリアへようこそ~