学习数据结构的时候遇到一个经典的回文链表问题
- 对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
如果有链表反转的基础，实现链表回文判断就简单的多，如果对反转链表不熟悉，可以参考这篇博客。
思路很简单，先找到链表的中间Node，采用的快慢指针法。
- 慢指针一次走一步，快指针一次走两步，当快指针触底的时候，慢指针到达了重点，如果链表总数是偶数，则慢指针停在相对左边的Node上。
- 找到中点后，对中点后面的链表进行反转。
- 从头尾开始向中间移步，每次比较是否相同。
/**
* @author axin
* @since 2019-09-29
*/
public class PalindromeList {
@Data
static class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
//第一步找到中点
//从中点开始将后续结点反转
//两遍开始next比较直到相遇
public static boolean isPalindrome(ListNode head) {
if(head==null||head.next==null) return true;
if(head.next.next==null){
return head.val == head.next.val;
}
ListNode one = head.next;
ListNode two = head.next.next;
while(two.next!=null&&two.next.next!=null){
one = one.next;
two = two.next.next;
}
//链表倒转
ListNode pre = null;
ListNode temp = null;
while(one!=null){
temp = one.next;
one.next = pre;
pre=one;
one = temp;
}
ListNode tail = pre;
//头尾比较
while(head!=null){
if(head.val!=tail.val) return false;
head = head.next;
tail = tail.next;
}
return true;
}
public static void main(String[] args) {
ListNode node7 = new ListNode(1);
ListNode node6 = new ListNode(2);
ListNode node5 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node3 = new ListNode(3);
ListNode node2 = new ListNode(2);
ListNode node1 = new ListNode(1);
node6.setNext(node7);
node5.setNext(node6);
node4.setNext(node5);
node3.setNext(node4);
node2.setNext(node3);
node1.setNext(node2);
System.out.println("===="+isPalindrome(node1));
}
}