Leetcode原题
思路
理解题，什么是回文链表呢。就是我们无论成正序还是倒序得到的值都是一样的。比如 1-2-3-3-2-1 或
1-2-1 、1-2-3-2-1。 而 1-2-3 或 1-2 这样的正序和倒序结果不一致的当然就不是了。
方法1 遍历数组比较
思路就是我们把这个链表的的所有数据，存到一个数组中，然后我们正序和逆序来比较值是否相同，直到下标相同为止，没有出现不同值。说明是回文链表。因为实现方法比较简单，而且这种实现也不符合题目空间复杂度O(1)的要求。所以就不编写了
方法2 快慢双指针
思路是：
1.分别使用2个指针，一个是快指针fastPro.一个是慢指针slowPro。
2.遍历链表，每一次移动快指针每次移动2步，慢指针移动1步，直走快指针走到末尾。如原链表： 1-2-3-3-2-1
那么快指针 1-3-2-null. 慢指针： 1-2-3-3
3.走到末尾快值针的值有2种情况。如果链表的长度是偶数，那么快指针走到末尾等于null。
如果链表长度为奇数，那么快指针走到到末尾的时候不为空。这个时候就要做特殊处理，将慢指针往后挪一位。
4. 慢指针此时指向的节点反转。 如刚好走到3. 后面还剩 2-1 。 那么接下来反转链表得到的就是1-2-3
将快指针指向原链表头
5.遍历从头比较慢指针指向的链表反转得到的1-2-3 和 head链表【1-2-3-3-2-1】。
6.如果比较中途值不同说明不是回文，否则为回文链表
public boolean isPalindrome(ListNode head) { ListNode fastPro = head; //分别定义2个快慢指针 ListNode slowPro = head; while(fastPro !=null && fastPro.next != null){ fastPro =fastPro.next.next; //快指针1次走2步 slowPro = slowPro.next; //慢指针1次走1步 } //上面的逻辑：快指针走到末尾要么等于null或不为空.快指针移动了几次，慢指针也移动几次 if(fastPro!=null) { //快指针不为空时,慢指针要特殊处理.往右移动一步 slowPro =slowPro.next; } //慢指针然后从此时的位置开始.反转链表: 3->2->1 1->2->3 slowPro =resver(slowPro); //此时快指针指向原链表头节点 fastPro =head; //比较两节点值是否相同，出现不相同的说明不是回文链表 while(slowPro!= null){ if(fastPro.val != slowPro.val){ return false; } fastPro =fastPro.next; slowPro =slowPro.next; } return true; } //反转链表 public ListNode resver(ListNode head){ ListNode curr =head; ListNode pre= null; while (curr!=null){ ListNode next= curr.next; curr.next = pre; pre =curr; curr =next; } return pre; }
方法三 快慢双指针进阶
看了一下官网的评论区还有更高级的写法。就是将方法2里的反转链表和第一步快慢指针合并为同步操作。确实效率更高一些。
public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) { return true; } ListNode slow = head, fast = head; ListNode pre = head, prepre = null; while(fast != null && fast.next != null) { pre = slow; slow = slow.next; fast = fast.next.next; pre.next = prepre; prepre = pre; } if(fast != null) { slow = slow.next; } while(pre != null && slow != null) { if(pre.val != slow.val) { return false; } pre = pre.next; slow = slow.next; } return true; }
有兴趣的老爷，还可以关注我的公众号【一起收破烂】，回复【006】获取 最新java面试资料以及简历模型120套哦~
