《LeetCode力扣练习》第234题 回文链表 Java_234. java回文链表 给你一个单链表的头节点 head ,请你判断该链表是否为回文链表

《LeetCode力扣练习》第234题 回文链表 Java

一、资源

• 题目：

  给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

  示例 1：

  

  输入：head = [1,2,2,1]
  输出：true

  示例 2：

  

  输入：head = [1,2]
  输出：false

  提示：

  链表中节点数目在范围[1, 105] 内
  0 <= Node.val <= 9
  1
  2

  进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

  来源：力扣（LeetCode）
  链接：https://leetcode-cn.com/problems/palindrome-linked-list
  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 上代码（经过线上OJ测试）

  /**
   * Created with IntelliJ IDEA.
   *
   * @author : DuZhenYang
   * @version : 2022.03.01  18:01:48
   * description :
   */
  public class LeetCode {
  
  
      public class ListNode {
          int val;
          ListNode next;
  
          ListNode() {
          }
  
          ListNode(int val) {
              this.val = val;
          }
  
          ListNode(int val, ListNode next) {
              this.val = val;
              this.next = next;
          }
      }
  
      public boolean isPalindrome(ListNode head) {
          if (head == null) {
              return true;
          }
  
          ListNode firstHalfEnd = endOfFirstHalf(head);
          ListNode secondHalfStart = reverseList(firstHalfEnd.next);
  
          ListNode ptr1 = head;
          ListNode ptr2 = secondHalfStart;
          boolean result = true;
  
          while (ptr2 != null && result) {
              if (ptr1.val != ptr2.val) {
                  result = false;
              }
              ptr1 = ptr1.next;
              ptr2 = ptr2.next;
          }
  
          firstHalfEnd.next = reverseList(secondHalfStart);
          return result;
      }
  
      private ListNode reverseList(ListNode head) {
          ListNode pre = null;
          ListNode current = head;
          ListNode next;
  
          while (current != null) {
              next = current.next;
              current.next = pre;
              pre = current;
              current = next;
          }
          return pre;
      }
  
      private ListNode endOfFirstHalf(ListNode head) {
          ListNode slow = head;
          ListNode fast = head;
  
          while (fast.next != null && fast.next.next != null) {
              slow = slow.next;
              fast = fast.next.next;
          }
          return slow;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76