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:統計長
チェーンテーブルの長さを統計し、再び遍歴して、長さの半分のノードを取り出すことができます.
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

質問やアドバイスがあれば、コメントエリアへようこそ~