算法之验证输入是否为回文(链表)
2020-05-20 本文已影响0人
木子小三金
package list;
/**
* @ClassName PalindromeLink
* @Description 单链表形式验证输入是否为回文
* @Author lixin
* @Date 2020/5/18 10:47 上午
*/
public class PalindromeLink {
/**
* 输入链表是否为回文
* 思路 :
* 1、通过"快慢指针"方式 ,创建2个指针,快指针每次向下走2步,慢指针每次向下走1步,当快指针到最后一个节点时,慢指针指向的即为中间节点
* 2、慢指针每次向后迁移一个节点后,反转走过的节点。
* 3、找到中间指针后,创建一个新指针,指向中间节点,然后慢指针继续向下单次移动一个节点,新指针向下单次移动一个节点,对比两个节点内容,如果不相等,则不是回文 ,全部相等则为回文。
* 4、注意链表奇偶数区别
* @param head
* @return
*/
public boolean isPalindrome(Node head){
Node fast = head;
Node slow = head;
Node next = slow.next;
while(true){
if(null == fast || null == fast.next || null == fast.next.next){
break;
}
/**
* 快指针向下走2步,这里要先移动快指针,否则慢指针批转后,会影响快指针移动
*/
fast = fast.next.next;
/**
* 慢指针向下走1步,并反转经过的节点
* 要点:
* 1、需要记录3个指针:当前指针、上一节点、下一节点
* 2、当前指针向后移动
* 3、反转指向关系
*/
Node pre = slow; //记录上一节点
slow = next; //当前指针向后移动
next = slow.next; //记录下一节点
pre.next = null; //删除上一节点的next
slow.next = pre; //反转
}
/**
* 如果链表长度奇偶与快指针结束关系
* 长度奇数:fast.next == null
* 长度偶数:fast.next != null
*
* 当链表长度为奇数时,跳过中间节点,从反转后的第一个节点开始比较
*/
if(null == fast.next){
slow = slow.next;
}
boolean palindrome = true;
while(true){
if(null == slow || null == next){
break;
}
if(slow.data != next.data){
palindrome = false;
break;
}
slow = slow.next;
next = next.next;
}
return palindrome;
}
public static void main(String[] args) {
ListOperator operator = new ListOperator();
/**
* 数组转链表,可自行实现
*/
Node head = operator.fromArray(new Integer[]{1,2,3,3,2,1});
PalindromeLink link = new PalindromeLink();
System.out.println(link.isPalindrome(head));
}
}