234. 回文链表

题目描述

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

输入输出

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

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

基本思路

  1. slow和fast双指针同时从head开始走 slow走一步 fast走两步
    1. 如果链表数量为奇数1->2->3->2->1->null slow 在第二个2 fast在null
    2. 如果链表数量为偶数1->2->2->1->null slow在3 fast在1 此时slow要往后移一位
  2. 从slow这个位置开始到最后进行反转 依次比较每个值是否相等
  3. tip: 若想不影响链表结构 可以p.next = reverse(q); 恢复

java实现

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
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head, p = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast != null){
            slow = slow.next;
        }
        ListNode right = reverse(slow);
        while(right != null){
            if(right.val != p.val){
                return false;
            }
            right = right.next;
            p = p.next;
        }
        return true;
    }
    public ListNode reverse(ListNode head){
        ListNode pre = null, cur = head;
        while(cur != null){
            ListNode new_head = cur.next;
            cur.next = pre;
            pre = cur;
            cur = new_head;
        }
        return pre;
    }
}