回文リンクリストリートコードソリューション


難易度 簡単に
よく聞かれる Adobe Amazon (アマゾン) Apple ブルームバーグ キャピタルワン Cisco Facebook Google つかむ インテル IXL マイクロソフト ヌタニクス オラクル Paytm Snapchat ユーバー Yandexの
リンクリスト XNUMXつのポインタ

問題「回文リンクリスト」では、与えられた単一の整数かどうかをチェックする必要があります リンクリスト 回文であるかどうか。

List = {1 -> 2 -> 3 -> 2 -> 1}
true

説明#1:最初から後ろまでのすべての要素の値が同じであるため、リストは回文です。

List = {1 -> 2 -> 3 -> 4 -> 5}
false

説明#2:前後の要素が同じではないため、リストは回文ではありません。

アプローチ(再帰)

これは、パリンドロームのプロパティをチェックするために、配列の後ろからノードの詳細を取得する必要があることに気付くのは簡単です。 この場合、 単独で リンクリストは、任意のノードに到達するために前方にのみ反復できることを意味します。 したがって、ノードを後ろから保持するためにいくつかのデータ構造を使用することが重要になります。 スタック 最新のノードを最上位に保持するため、可能なオプションです。 同様に再帰を使用することもできます。 再帰は、ノード値を逆の順序で取得するための洗練された方法です。 理解を深めるために、以下の一般的な擬似コードを検討してください。

inorderTraversal(root)
{
    if(root == null)
        return;
    inorderTraversal(root.left);
    print(root.data);
    inorderTraversal(root.right);
}

上記のコードは最初に出力します 左 ノード自体の値を出力する前に、任意のルートの左の子に移動する関数を再帰的に呼び出すため、ツリー内のノード。 同様に、私たちは使用することができます 再帰 最初に最後のノードに移動し、関数がバックトラックするときに、ノード値を逆の順序で取得します。 再帰の影響を受けない変数を使用して前方に反復します。 このようにして、再帰によって取得された順方向イテレータの値と逆方向ノードの値を比較して、要素を比較できます。

アルゴリズム

  1. 機能 isPalindrome() を含むリストかどうかを返すために使用されます  回文かどうか
  2. 名前の付いたクラスのデータメンバーを宣言します フロント 順方向反復のためにノードを格納する
  3. In isPalindrom():
    • 初期化します フロント=ヘッド
    • palindromeCheck(head)を返す
  4. In palindromeCheck(現在):
    • If 現在 is ヌル:
      • リターン true
    • If palindromeCheck(現在.次) is false:
      • リターン false
    • If 現在の価値 is Studio上ではサポートされていません。 に等しい フロント.バリュー
      • リターン false
    • フロントを次のようにインクリメントします。
      • フロント=フロント。次へ
    • リターン true すべてのチェックを実行したので
  5. 結果を印刷する

回文リンクリストリートコードソリューションの実装

C ++プログラム

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

bool palindromeCheck(listNode* head)
{
    if(head == NULL)
        return true;
    if(!palindromeCheck(head->next))
        return false;
    if(front->value != head->value)
        return false;
    front = front->next;
    return true;
}

bool isPalindrome(listNode* head)
{
    front = head;
    return palindromeCheck(head);
}

int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);
    head->next->next->next = new listNode(2);
    head->next->next->next->next = new listNode(1);

    cout << (isPalindrome(head) ? "true\n" : "false\n");
    return 0;
}

Javaプログラム

class listNode
{
    int value;
    listNode next;
    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class palindrome_linked_list
{
    static listNode front;
    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(2);
        head.next.next.next.next = new listNode(1);

        System.out.println((isPalindrome(head)) ? "true" : "false");
    }

    static boolean palindromeCheck(listNode head)
    {
        if(head == null)
            return true;
        if(!palindromeCheck(head.next))
            return false;
        if(front.value != head.value)
            return false;
        front = front.next;
        return true;
    }

    static boolean isPalindrome(listNode head)
    {
        front = head;
        return palindromeCheck(head);
    }
}
true

回文リンクリストリートコードソリューションの複雑さの分析

時間の複雑さ

オン) 再帰を使用してリストをXNUMX回トラバースするとき。 ここで、N =リスト内のノードの数。

スペースの複雑さ

オン) 再帰関数を呼び出して、作成するすべてのノードをチェックします N メモリ内のスタックフレーム。

アプローチ(他の半分を逆にする)

再帰で使用されるスペースを取り除く唯一の方法は、指定されたリストをインプレースで変更することです。 リンクリストの後半を逆にしてから、両方の半分にXNUMXつの順方向イテレータを使用して、対応する値が等しいかどうかを確認します。 このプロセスでは、次のことを行う必要があります。

  • リストの真ん中を見つけて、後半を逆にすることができます。
  • リストの後半を逆にする関数を作成します
  • 前半と後半が等しいか確認してください

上記のすべては線形時間で行うことができます。 リンクリストを逆にした後、後半が完了するまでチェックを開始します。

回文リンクリストリートコードソリューション

アルゴリズム

  1. If is ヌル:
    • 真を返す
  2. を使用してリンクリストの中央を検索します middleOfList( 関数:
    • XNUMXつのポインタを初期化します 遅く 速いです 両方ともリストの先頭を指しています
    • まで 速い.次 fast.next.next 両方とも Studio上ではサポートされていません。 ヌル:
      1. インクリメント 遅く 1による 遅い= slow.next
      2. インクリメント 速いです 2による fast = fast.next.next
    • 遅く ポインタがリストの中央を指すようになりました
    • リターン 遅く
  3. 次に、リストの後半を逆にして呼び出します reverseList(head = 真ん中.次) function
    • 初期化 前のページ = ヌル
    • while nullではありません:
      • 次のノードを一時変数に格納します。 次の
      • を使用してポインタの方向を逆にします head.next = prev
      • 前=頭
      • を使用してリストを先に進めます 頭=次
    • リターン 前のページ
  4. ここで、XNUMXつのポインタを初期化します ptr1 ptr2 両方の半分を反復する:
    1. ptr1 =頭
    2. ptr2 =開始 後半の
    3. while ptr2 nullではありません:
      1. if ptr1. 等しくない ptr2.
        1. リターン false
    4. リターン true 前半と後半にすべてのノードをチェックしたので
  5. 結果を印刷する

回文リンクリストリートコードソリューションの実装

C ++プログラム

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

listNode* middleOfList(listNode* head)
{
    listNode *slow = head , *fast = head;
    while(fast->next != NULL && fast->next->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

listNode* reverseList(listNode* head)
{
    listNode *prev = NULL;
    while(head != NULL)
    {
        listNode* next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

bool isPalindrome(listNode* head)
{
    if(head == NULL)
        return true;
    listNode* middleNode = middleOfList(head);
    listNode* startOfSecondHalf = reverseList(middleNode->next);

    listNode *ptr1 = head , *ptr2 = startOfSecondHalf;
    while(ptr2 != NULL)
    {
        if(ptr1->value != ptr2->value)
            return false;
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return true;
}

int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);
    head->next->next->next = new listNode(2);
    head->next->next->next->next = new listNode(1);

    cout << (isPalindrome(head) ? "true\n" : "false\n");
    return 0;
}

Javaプログラム

class listNode
{
    int value;
    listNode next;
    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class palindrome_linked_list
{
    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(2);
        head.next.next.next.next = new listNode(1);

        System.out.println((isPalindrome(head)) ? "true" : "false");
    }

    static listNode middleOfList(listNode head)
    {
        listNode slow = head , fast = head;
        while(fast.next != null && fast.next.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    static listNode reverseList(listNode head)
    {
        listNode prev = null;
        while(head != null)
        {
            listNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    static boolean isPalindrome(listNode head)
    {
        if(head == null)
            return true;
        listNode middleNode = middleOfList(head);
        listNode startOfSecondHalf = reverseList(middleNode.next);

        listNode ptr1 = head , ptr2 = startOfSecondHalf;
        while(ptr2 != null)
        {
            if(ptr1.value != ptr2.value)
                return false;
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return true;
    }
}
true

回文リンクリストリートコードソリューションの複雑さの分析

時間の複雑さ

オン) 線形ループを使用してリストの中央を見つけ、それを逆にして、両方の半分を比較します。 ここに、 N =リストのサイズ。

スペースの複雑さ

O(1) 一定の余分なスペースのみを使用するためです。