大佬教程收集整理的这篇文章主要介绍了剑指 Offer II 027. 回文链表，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

剑指 Offer II 027. 回文链表

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

方法一：将值复制到数组中后用双指针法

列表的概要讲述：

有两种常用的列表实现，分别为数组列表和链表。如果我们想要在列表中存储值，它的实现是这样的：

• 数组列表底层是使用数组存储值，我们可以通过索引在 O(1) 的时间访问列表任何位置的值，这是由基于内存寻址的方式。
• 链表存储的是称为节点的对象，每个节点保存一个值和指向下一个节点的指针。访问某个特定索引的节点需要 O(n) 的时间，因为要通过指针获取到下一个位置的节点。

确定数组列表是否回文很简单，我们可以使用双指针法来比较两端的元素，并向中间移动。一个指针从起点向中间移动，另一个指针从终点向中间移动。这需要 O(n) 的时间，因为访问每个元素的时间是 O(1)，而有 n 个元素要访问。

然而同样的方法在链表上操作并不简单，因为不论是正向访问还是反向访问都不是 O(1)。而将链表的值复制到数组列表中是 O(n)，因此最简单的方法就是将链表的值复制到数组列表中，再使用双指针法判断。

大体的思路：

1.复制链表到数组列表中
2.使用双指针判断是否回文

具体的实现：

第一步，我们需要遍历链表将值复制道数组中，我们用 currentNode 指向当前的节点。每次迭代向数组中添加 currentNode.val 并更新currentNode = currentNode.next 。当currentNode==null 时停止循环。

第二步，我们在起点放个指针，在结尾放一个指针，每一次迭代判断两个指针指向的元素是否相同，若不同，return false。相同，则相反。相同则将两个指针向中间移动，并继续判断，直到两个指针相遇。

/**
 * 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 {
    public Boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<Integer>();

        //遍历量表逐个将值放到数组中去
        ListNode currnetNode = head;
        while(currnetNode!=null){
            list.add(currnetNode.val);
            currnetNode=currnetNode.next;
        }

        //在数组的两端设置两个指针
        int front = 0;
        int BACk =list.size()-1;
         while(front<BACk){
             if(!list.get(front).equals(list.get(BACk))){
                 return false;
             }else{
                 front++;
                 BACk--;
             }
         }
         return true;
    }
}

方法二：递归

递归为我们提供了一种优雅的方式来方向遍历节点。

function print_values_in_reverse(ListNode head){
  if(head!=null){
    print_values_in_reverse(head.next);
  }
}

如果使用递归反向迭代节点，同时使用递归函数外的变量向前迭代，就可以判断链表是否为回文。

实现思路：

currentNode 指针是先到尾节点，由于递归的特性是从后往前比较。frontPointer 是递归函数外的指针。
若currentNode.val != frontPointer.val 则返回false。
反之，frontPointer 向前移动并返回true。

/**
 * 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 {

    private ListNode frontPointer;

    private Boolean recursivelycheck(ListNode currentNodE) {
        if (currentNode != null) {
            if (!recursivelycheck(currentNode.next)) {
                return false;
            }
            if (currentNode.val != frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }

    public Boolean isPalindrome(ListNode head) {
        frontPointer = head;
        return recursivelycheck(head);
    }

}

大佬总结

以上是大佬教程为你收集整理的剑指 Offer II 027. 回文链表全部内容，希望文章能够帮你解决剑指 Offer II 027. 回文链表所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。