中判断回文的代码_LeetCode(234. 回文链表) 题解

234. 回文链表

题目

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

何为回文？

维基百科是这样介绍的：

回文，亦称回环，是正读反读都能读通的句子，亦有将文字排列成圆圈者，是一种修辞方式和文字游戏。

北宋文学家苏轼创作的一首名为《菩萨蛮·回文夏闺怨》的词，就用到了回文的修辞方式。

菩萨蛮·回文夏闺怨 

苏轼

柳庭风静人眠昼。昼眠人静风庭柳。

香汗薄衫凉。凉衫薄汗香。

手红冰碗藕。藕碗冰红手。

郎笑藕丝长。长丝藕笑郎。

这首《夏闺怨》大意呢是上片写闺人昼寝的情景，下片写醒后的怨思。各位看官感受一下回文的妙处，至于诗歌赏析暂且按住不表，有兴趣的看官可以自行查阅解析。

回顾

之前做过判断回文的相似题，还记得怎么解吗：LeetCode(125. 验证回文串) 题解。

当时提到了两种解法，一种原地翻转，一种双指针。同样也适用于解这道题。区别在于125题是字符串，本题是单链表。基于单链表的线性的链式存储结构的特点，这里就需要一点点小技巧进行相应的转化与处理。

思路1-原地翻转

对于字符串的原地翻转，可以通过Java的API实现，也可以使用双指针的办法，手写一个原地翻转的函数。单链表，不能访问前驱节点，可以利用栈后入先出的特性，遍历一遍单链表将链表中的节点入栈，然后栈顶元素依次出栈和链表遍历比较，判断翻转后的链表是否与原链表相等。

上代码

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public boolean isPalindrome(ListNode head) {        if(head == null || head.next == null) return true;        Stack stack = new Stack<>();        ListNode node = head;        while(node != null){            stack.push(node);            node = node.next;        }        while(head != null && !stack.isEmpty()){            ListNode tmpNode = stack.pop();            if(head.val != tmpNode.val) return false;            head = head.next;        }        return true;    }}
           

思路2-双指针法之快慢指针

对于字符串的双指针法，初始时，左右指针分别指向字符串的两侧，左指针左移，右指针右移，每次移动一步，并判断这两个指针指向的字符是否相同。对于链表，右指针右移的部分应该怎么处理呢？可以通过快慢指针法找到链表的中间节点，将后半部分翻转，然后两个链表依次遍历进行比较。后半部分翻转后的遍历相当于右指针右移部分。

上代码

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public boolean isPalindrome(ListNode head) {        if(head == null || head.next == null) return true;        //快慢指针        ListNode fastNode = head;        ListNode slowNode = head;        //快指针走两步 慢指针走一步 找到链表中点        while(fastNode.next != null && fastNode.next.next != null){            slowNode = slowNode.next;            fastNode = fastNode.next.next;        }        //将后半部分反转        ListNode newHead = null;        ListNode curr = slowNode.next;        while(curr != null){            ListNode tmpNode = curr.next;            curr.next = newHead;            newHead = curr;            curr = tmpNode;        }        //两部分进行比较判断        while(head != null && newHead != null){            if(head.val != newHead.val) return false;            head = head.next;            newHead = newHead.next;        }        return true;    }}
           

分析

这种解法的优点在于没有开辟额外的内存空间，算法的空间复杂度为O(1)。

思路3-双指针法

双指针法需要左右指针进行遍历判断，对于链表无法实现，可将链表进行转换，将其复制到列表或数组中，使之可以使用左右指针相向而行的方法进行判断。

上代码

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public boolean isPalindrome(ListNode head) {        if(head == null || head.next == null) return true;        List list = new ArrayList<>();        while(head != null){            list.add(head);            head = head.next;        }        int left = 0;        int right = list.size() - 1;        while(left < right){            if(list.get(left).val != list.get(right).val) return false;            left ++;            right --;        }        return true;    }}
           

思路4-递归

还有一种递归的解法，参照 思路2-原地翻转的思想，链表可以使用递归的方法进行逆序遍历，那么将逆序遍历的结果与原链表进行比较就可以完成判断。参考官方题解链接[1]。

上代码

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    ListNode front = null;    public boolean isPalindrome(ListNode head) {        if(head == null || head.next == null) return true;        front = head;        return recursion(head);    }    public boolean recursion(ListNode head){        if(head == null) return true;        boolean res = recursion(head.next);        if(head.val != front.val) return false;        front = front.next;         return res;    }}
           

References

[1] https://leetcode-cn.com/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/

程序员画工师｜欢迎关注

持续分享Java相关编程技术、数据结构与算法