题目

image.png

思路

  • 思路一：通过快慢指针找到中点，然后使用栈把后半部分保存。再通过出栈跟前一半进行比较，判断是否为回文链表
  • 思路二：通过计算模拟hash值来判断是否回文
  • 思路三：通过快慢指针找到中点，将后半部分逆转，再判断前一部分和后一部分是否一致

代码

  1.       public boolean isPalindrome(ListNode head) {
  2.         if(head == null) return true;
  3.         ListNode fast = head, slow = head, end = null;
  4.         boolean flag = true;
  5.         while(fast != null) {
  6.              if(fast.next == null) {
  7.                  fast = fast.next;
  8.                  flag = false;
  9.              } else {
  10.                  fast = fast.next.next;
  11.                  slow = slow.next;
  12.              }
  13.         }
  14.         end = slow;
  15.         fast = head;
  16.         if(!flag)  slow = slow.next;
  17.         Stack<ListNode> stack = new Stack<>();
  18.         while(slow != null) {
  19.             stack.push(slow);
  20.             slow = slow.next;
  21.         }
  22.         while(!stack.isEmpty() && !fast.equals(end)) {
  23.             if(fast.val == stack.pop().val) {
  24.                 fast = fast.next;
  25.             }else return false;
  26.         }
  27.         if(fast.equals(end) && stack.size() == 0) return true;
  28.         return false;
  29.     }
  31.      public boolean isPalindrome(ListNode head) {
  32.         float s1 = 0,s2 = 0,t = 1;
  34.         while(head != null) {
  35.             s1 = s1*10 + head.val;
  36.             s2 = s2 + t*head.val;
  37.             t = t*10;
  38.             head = head.next;
  39.         }
  40.         return s1 == s2;
  41.      }
  43.     //思路三
  44.     public boolean isPalindrome(ListNode head) {
  45.         if (head == null) return true;
  46.         ListNode fast = head, slow = head;
  47.         while (fast != null && fast.next != null) {
  48.             slow = slow.next;
  49.             fast = fast.next == null ? fast.next : fast.next.next;
  50.         }
  51.         ListNode prev = null;
  52.         while (slow != null) {
  53.             ListNode t = slow.next;
  54.             slow.next = prev;
  55.             prev = slow;
  56.             slow = t;
  57.         }
  58.         while (head != null && prev != null) {
  59.             if (head.val != prev.val) return false;
  60.             head = head.next;
  61.             prev = prev.next;
  62.         }
  63.         return true;
  64.     }

回文链表