234.回文チェーンテーブル_詳細解答(java)

文書ディレクトリ

234.回文チェーン表

構想とコード(java)

方法一、二重サイクル、(比較的分かりやすい)

方法2、速い遅いポインタ、(少し難しい)

方法3、再帰、(少し難しい)

参考資料

234.回文チェーン表
チェーンテーブルが返信チェーンテーブルであるかどうかを判断してください.
例1:

  : 1->2
  : false

例2:

  : 1->2->2->1
  : true

進級:O(n)時間の複雑さとO(1)空間の複雑さでこの問題を解決できますか?
構想とコード(java)
方法1、ダブルサイクル、(比較的わかりやすい)
簡単に言えば、チェーンテーブルの要素をすべて配列に入れて、配列がランダムにアクセスできる特性を利用して、2つのポインタ、1つは頭にプラスして、1つは尾で減らして、同じではありません直接retrun false.
1
2
3
2
1
ヘッドポインタ
—>
テールポインタ

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
		if(head==null || head.next==null) {
			return true;
		}
		java.util.ArrayList<Integer> arr = new java.util.ArrayList<Integer>();
		//      ，           
		while(head!=null) {
			arr.add(head.val);
			head = head.next;
		}
		int i = 0;
		int j = arr.size()-1;
		// i j    ，    ，    ，    
		//  i     j      ，     
		while(i<j) {
			if(arr.get(i).compareTo(arr.get(j))!=0) {
				return false;
			}
			++i;
			--j;
		}
		return true;        
    }
}

実行時間:4 ms、すべてのJavaコミットで23.46%のユーザーメモリ消費量:40.7 MBを破り、すべてのJavaコミットで97.70%のユーザーを破った
方法2、ポインタを速く遅くして、(少し難しい)
2つのポインタを使用してチェーンテーブルの中点を見つけ、遅いポインタは前に進むたびに、速いポインタは2ステップ前進します.遅いポインタが進む過程で、チェーンテーブルの前半が逆シーケンスになるようにnextポインタを変更します.最後に、中点の両側のチェーンテーブルが等しいかどうかを比較します.

class Solution {
  public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
      return true;
    }

    ListNode prev = null;
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
      fast = fast.next.next;
      ListNode next = slow.next;
      slow.next = prev;
      prev = slow;
      slow = next;
    }

    if (fast != null) {
      slow = slow.next;
    }

    while (slow != null) {
      if (slow.val != prev.val) {
        return false;
      }
      slow = slow.next;
      prev = prev.next;
    }

    return true;
  }
}

実行時間:1 ms、すべてのJavaコミットで99.53%のユーザーメモリ消費量:41.5 MBを破り、すべてのJavaコミットで97.32%のユーザーを破った
方法3、再帰、(ちょっと難しい)

class Solution {

    private ListNode frontPointer;

    private boolean recursivelyCheck(ListNode currentNode) {
        if (currentNode != null) {
            if (!recursivelyCheck(currentNode.next)) return false;
            if (currentNode.val != frontPointer.val) return false;
            frontPointer = frontPointer.next;
        }
        return true;
    }

    public boolean isPalindrome(ListNode head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
}

から
参考資料
回文チェーンテーブル-leetcode回文チェーンテーブル-ブラシ問題