LeetCode234 回文链表多解

LeetCode234 回文链表

1. 解法一：将原始链表的值存入ArrayList中，然后将原始链表反转后值再存入ArrayList中，进行循环比较

2. 解法二：树结构是链表结构的衍生，二叉树的遍历对链表同样适用

   1. 链表也可以有前序遍历和后序遍历

      void traverse(ListNode head) {
          // 前序遍历代码
          traverse(head.next);
          // 后序遍历代码
      }
      

   2. 使用链表的后序遍历加上双指针完成

      class Solution {
          ListNode left;
          public boolean isPalindrome(ListNode head) {
              left = head;
              return traverse(head);
          }
          boolean traverse(ListNode right) {
              if (right == null) return true;
              boolean res = traverse(right.next);
              res = res && (right.val == left.val);
              left = left.next;
              return res;
          }
      }
      

   3. 代码分析：实际上就是将链表节点放入调用栈中，然后取出，这时元素的顺序就是反的

3. 解法三：对于解法二进行优化，可以通过快慢指针先找到链表的中点

   算法总体的时间复杂度 O(N)，空间复杂度 O(1)

   1. 使用快慢指针找到链表的中点，注意如果fast != null，即链表节点的个数为奇数，则可将slow后移一步

      

   2. 反转slow之后的链表reverse(slow)，看前文

   3. 使用左右指针比较

      ListNode left = head;
      ListNode right = reverse(slow);
      
      while (right != null) {
          if (left.val != right.val)
              return false;
          left = left.next;
          right = right.next;
      }
      return true;
      

   4. 完整代码

      class Solution {
          public boolean isPalindrome(ListNode head) {
              ListNode fast, slow, left;
              left = fast = slow = head;
              //使用快慢指针使slow指向中点
              while (fast != null && fast.next != null) {
                  slow = slow.next;
                  fast = fast.next.next;
              }
              //如果fast不为null，则证明链表个数为奇数，slow还能再进一步
              if (fast != null) {
                  slow = slow.next;
              }
      
              ListNode right = reverse(slow);
              while (right != null) {
                  if (left.val != right.val) {
                      return false;
                  }
                  left = left.next;
                  right = right.next;
              }
              return true;
          }
      
          ListNode reverse(ListNode head) {
              ListNode cur = head;
              ListNode pre = null;
              ListNode temp;
              while (cur != null) {
                  temp = cur.next;
                  cur.next = pre;
                  pre = cur;
                  cur = temp;
              }
              return pre;
          }
      }
      

4. 总结：寻找回文串是从中间向两端扩展，判断回文串是从两端向中间搜索。对于单链表，可以反转链表，可以利用链表的后序遍历，可以使用调用栈倒序处理