leetcode 题号#234 回文链表

本文主要是介绍leetcode 题号#234 回文链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

查看题目详情可点击此处。

题目

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

解题思路

首先理解回文的意思，回文就是正着读和反着读得到的结果都一样，那最直接的解题思路就是拷贝一份反转的链表，再与原链表从头结点开始比对，如果完全一致就是回文链表，但空间复杂度和时间复杂度都为 $O (n)$ ，为了把空间复杂度降低需要重新转换思路。

仔细思考，其实回文还有另外一种判断方式，就是从中间结点往头结点和尾结点方向读取，得到的结果是一样的，但题目给出的是单链表，如果是双向链表操作就会简单很多，单链表的情况只能把前半段链表反转，以中间结点作为头结点，头结点为前半段的尾结点，后半段链表也以中间结点为头结点，尾结点作为尾结点，这样循环比对每个结点，就可以判断回文。

要知晓链表的中间结点只能先获取整个链表的长度，奇数长度的链表中间结点分别是第 $n / 2$ 和 $n / 2 + 2$ 个结点，偶数结点的中间结点分别是第 $n / 2$ 和 $n / 2 + 1$ 个结点，得知中间结点的是链表中的第几个结点后，可以遍历获取中间结点作为头结点的同时对前半段链表进行反转，最后进行相应链表结点的比对即可，代码如下。

class Solution {public boolean isPalindrome(ListNode head) {if(head == null || head.next == null) {return true;}int len = getLinkLen(head);int leftHeadCounter = len / 2;ListNode[] halfHeads = findHalfHead(head, leftHeadCounter, len);ListNode leftHalfHead = halfHeads[0];ListNode rightHalfHead = halfHeads[1];ListNode leftCurr = leftHalfHead;ListNode rightCurr = rightHalfHead;while(leftCurr != null && rightCurr != null) {if(leftCurr.val != rightCurr.val) {break;}leftCurr = leftCurr.next;rightCurr = rightCurr.next;}return leftCurr == null && rightCurr == null;}public ListNode[] findHalfHead(ListNode head, int leftHeadCounter, int len) {ListNode[] halfHeads = new ListNode[2];ListNode curr = head;ListNode prevNode = null;ListNode reverseNode = null;int counter = 0;while(curr != null) {counter++;if(leftHeadCounter == counter) {halfHeads[0] = curr;break;}reverseNode = curr;curr = curr.next;prevNode = reverseLink(reverseNode, prevNode);}ListNode rightHalfHead = halfHeads[0].next;if(len % 2 == 1) {rightHalfHead = rightHalfHead.next;}halfHeads[1] = rightHalfHead;reverseLink(halfHeads[0], prevNode);return halfHeads;}public ListNode reverseLink(ListNode reverseNode, ListNode prevNode) {reverseNode.next = prevNode;return reverseNode;}public int getLinkLen(ListNode head) {int len = 0;ListNode curr = head;while(curr != null) {len++;curr = curr.next;}return len;}
}