234. 回文链表（简单）

谁践踏了优雅 2022-09-09 12:59 100阅读 0赞

Leetcode链接：[234. 回文链表][234.]

### 题目描述 ###

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

示例 1：

![在这里插入图片描述][2d92cc9ac67848a7809e985ab836fcfb.png]

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

示例 2：

![在这里插入图片描述][2a95c68f0eac40faa1ba0bd873d41ad9.png]

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

提示：

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

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

### 源码 ###

题解：快慢指针+反转链表

/**
     * Definition for singly-linked list.
     * 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; }
     * }
     */
    class Solution {
        
        public boolean isPalindrome(ListNode head) {
        
            ListNode fast = head;
            ListNode slow = head;
    
            while(fast != null && fast.next != null){
        
                fast = fast.next.next;
                slow = slow.next;
            }
    
            slow = reverse(slow);
            ListNode curr = head;
            while(slow != null){
        
                if(slow.val != curr.val) return false;
                slow = slow.next;
                curr = curr.next;
            }
    
            return true;
        }
    
        public ListNode reverse(ListNode head){
        
            ListNode prev = null;
            ListNode curr = head;
    
            while(curr != null){
        
                ListNode temp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = temp;
            }
            return prev;
        }
    }

[234.]: https://leetcode-cn.com/problems/palindrome-linked-list/
[2d92cc9ac67848a7809e985ab836fcfb.png]: /images/20220829/3ad3f82a00424715ab80f7d64fdef856.png
[2a95c68f0eac40faa1ba0bd873d41ad9.png]: /images/20220829/443b0227420d47fba731c1e2711de8d9.png