logo网站素材网站开发与软件开发

如何判断回文链表

题目描述

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

示例 1：

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

示例 2：

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

提示：

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

解题思路及代码

•         使用快慢指针法找到链表的中间节点，快指针每次走两步，慢指针每次走一步，当快指针到达链表尾部时，慢指针恰好到达中间节点。
•         根据是否有偶数个节点，将慢指针指向下一个节点，以确保慢指针指向后半部分链表的起始节点。
•         将后半部分链表反转。
•         逐一比较前半部分链表和反转后的后半部分链表的节点值，如果全部相同，则链表是回文的，否则不是。

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

结果展示