欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-05 09:48:19
学习数据结构的时候遇到一个经典的回文链表问题 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。 如果有链表反转的基础,实现链表回文判断就简单的多,如果对反转链表不熟悉,可以参考这篇 "博客" 。 思路很简单,先找到链表的中间Node,采用的快慢指针 ......

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

  • 对于一个链表,请设计一个时间复杂度为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;
    }
}