質問する

白駿:法林矮樹[青銅1]
leetcode: palindrome linked list [Easy]

ファリンドロンとは何ですか。

「回文」とも呼ばれ、文や単語の左右対称を指す.例えば、単語12321、文a man、a plan、a channel:panama(amanaplana c anonama).

質問する

共通

自然数を入力します.この自然数が法林症候群かどうかを確認する問題です.

白駿

範囲は1から999999までで、文字列形式で与えられます.

leetcode

範囲は1～100000です.文字列ではなく接続リストが付与されます.

に近づく

白駿-ファリンドロンの木には、ファリンドロンを得る方法がいくつかあります.文字列をコピーし、反転して文字が一致しているかどうかを確認できます.または、文字列をcollections.dequeに変換し、文字列を両側のpopに変換して、文字の一致/不一致を確認できます.ただし,本章では,単一の接続リストを用いて解析を試みる.

に答える

leetcodeに従って説明します.

上記の問題を解決するには大体2つの方法がある.

dequeに変換

接続リストのデータをループしてdequeを作成し、さっきの問題-アクセスで説明したようにdequeを使用して解くことができます.ただし,これは接続リストが十分に利用されていない解答であり,問題に必要な解答ではない.さらに、dequeを作成するために1回のループを実行し、文字列の長さの1/2を再度ループして確認し、ノードの値をコピーしてdequeに挿入する必要があるため、追加の時間が発生します.

流路法を用いて解く

他の材料構造を作成することなく、ランナーテクノロジーを使用して問題を解決できます.

流路技術とは何ですか。

ランナーテクノロジーとは、2つの開始ノード(head)を宣言し、1つはセルを移動し、もう1つは2つのセルを移動することで、接続リストの中間点を検索します.
この問題では、中間点に左に移動すると、既存のノードを使用して逆リストが作成され、左と逆リストを使用してファリンドロンがチェックされます.

オーダー

逆順序リストの作成

[Turn 1]

前後はすべて頭部に位置している.

2グリッド

の右側を移動し、左側のポイントでtmpを宣言し、左に1グリッド移動します.

tmpのノードを「逆接続」リストに移動します.

[Turn 2]

のように、右側に2マス、左側にtmp、左側に1マス移動します.

tmpにあるノードを逆headの後部に追加します.

[Turn 3]

rightの次の部分が空、すなわち上部にあるため、回転は終了する.
奇数長はrightですが、nextはNull、偶数長はnullです.したがって,以下のコードにも書かれているがwhile文を迂回する際には,条件をright and right.nextとする.

ファリンドロンの確認

現在は左と逆のファリンドロンを確認することしか残っていません.その前に、権利の状態を理解しなければなりません.奇数の長さの場合は、ちょうど真ん中にあるため、セルを左に移動します.

の左側と逆方向の接続リストの長さは一致しているため、上部に達する前にデータが一致しているかどうかを検証するだけでよい.中間値が正しくない場合は繰り返し文から終了し、逆方向がNoneの場合はFalse、NoneまたはTrueとして出力されます.

コード#コード#

Leetcode

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        
        rev = None # 역순 리스트
        left = right = head
        
        while right and right.next:
            right = right.next.next # 2칸씩
            
            # 한 칸 씩, 그리고 역순 리스트에 데이터 추가
            tmp = left
            left = left.next
            
            prev_node, new_node = rev, tmp
            new_node.next = prev_node
            rev = new_node
        
        if right:
            # 해당 문자열은 홀수, 따라서 left가 한 칸 더 이동해서 맞춘다
            left = left.next
            
        
        while rev and rev.val == left.val:
            rev, left = rev.next, left.next
        
        # rev가 None일 경우 끝까지 확인했기 때문에 True다
        # 따라서 not rev -> 팰린드롬 O
        return not rev
        

Bakjoon

接続リストにアクセスできないため、接続リストを作成するタスクを追加する必要があります.

class Node:
    def __init__(self, val: str):
        self.val = val
        self.next = None        
class LinkedList:
    def __init__(self):
        self.head = None
    def push(self, val):
        # 입력 연산을 줄이기 위해 Queue 스타일로 구현
        if self.head == None:
            self.head = Node(val)
        else:
            new_node, next_node = Node(val), self.head
            new_node.next, self.head = next_node, new_node

def use_runner(L: LinkedList):

    head = L.head
    left = right = head
    reverse = None # 역순 리스트

    while right and right.next:
        # 오른쪽 두칸 이동
        right = right.next.next
        
        tmp = left # 역순 리스트를 만들기 위한 node
        left = left.next # 한 칸 이동
        
        # 역순 리스트 생성
        prev_reverse, new_reverse = reverse, tmp
        new_reverse.next = prev_reverse
        reverse = new_reverse

        # 또는 이렇게 표현 가능
        # reverse, reverse.next, left = left, reverse, left.next

    if right:
        # right에 노드가 남아있는 경우 -> 노드 길이가 홀수
        # 한칸 이동한다
        left = left.next

    while reverse:
        if left.val != reverse.val:
            # 다르면 팰린드롬이 아니다
            return "no"
        left, reverse = left.next, reverse.next
    return "yes"

def palindrome(S: str):

    # 연결 리스트 생성
    l = LinkedList()
    for char in S:
        l.push(char)
    return use_runner(l)

S = input()
R = []
while S != '0':

    # Check 펠린드롬
    R.append(palindrome(S))
    S = input()

print('\n'.join(R))