链表回文判断(基于链表反转)—Java实现

Java基础

浏览数:99

2019-8-18

AD:资源代下载服务

学习数据结构的时候遇到一个经典的回文链表问题

  • 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。

如果有链表反转的基础,实现链表回文判断就简单的多,如果对反转链表不熟悉,可以参考这篇博客

思路很简单,先找到链表的中间Node,采用的快慢指针法。

  • 慢指针一次走一步,快指针一次走两步,当快指针触底的时候,慢指针到达了重点,如果链表总数是偶数,则慢指针停在相对左边的Node上。
  • 找到中点后,对中点后面的链表进行反转。
  • 从头尾开始向中间移步,每次比较是否相同。
import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    //第一步找到中点
    //从中点开始将后续结点反转
    //两遍开始next比较直到相遇
    public boolean chkPalindrome(ListNode A) {
        ListNode node1 = A;
        ListNode node2 = A;
        while(node2.next!=null&&node2.next.next!=null){
            node1=node1.next;
            node2=node2.next.next;
        }
        ListNode head2 = node1.next;
        //反转链表过程,推荐采用遍历法
        ListNode temp = null;
        ListNode pre = null;
        while(head2!=null){
            temp = head2.next;
            head2.next = pre;
            pre = head2;
            head2=temp;
        }
        //对比过程
        ListNode n1 = A;
        ListNode n2 = pre; //最后一个节点
        while(n1.next!=null){
            if(n1.val!=n2.val){
                return false;
            }
            n1=n1.next;
            n2=n2.next;
        }
        return true;
    }
}

作者:上帝爱吃苹果-Soochow