题目描述：
解题思路：
判断一个单向链表是否是回文链表，并且要求O（n）的时间复杂度和O（1）的空间复杂度。
方法有以下几种：
1、遍历整个链表，将链表每个节点的值记录在数组中，再判断数组是不是一个回文数组，时间复杂度为O（n），但空间复杂度也为O（n），不满足空间复杂度要求。
2、利用栈先进后出的性质，将链表前半段压入栈中，再逐个弹出与链表后半段比较。时间复杂度O（n），但仍然需要n/2的栈空间，空间复杂度为O（n）。（起初选用了这种方法）
3、反转链表法，将链表后半段原地翻转，再将前半段、后半段依次比较，判断是否相等，时间复杂度O（n），空间复杂度为O（1）满足题目要求。链表翻转可以参考LeetCode 206 Reverse Linked List的代码。
第三种方法的核心在于，维护两个指针，慢指针一次移动一个，快指针一次移动两个，这样的结果是，快指针到达末尾时，慢指针到达中间。
模拟如下图：
Java代码：
1 //public class LeetCode234为测试代码 2 public class LeetCode234{ 3 public static void main(String[] args) { 4 ListNode n1=new ListNode(1),n2=new ListNode(2),n3=new ListNode(4),n4=new ListNode(2),n5=new ListNode(1); 5 ListNode head=n1; 6 n1.next=n2; 7 n2.next=n3; 8 n3.next=n4; 9 n4.next=n5; 10 System.out.print("链表"+n1.val+"->"+n2.val+"->"+n3.val+"->"+n4.val+"->"+n5.val+"是否是回文链表："); 11 System.out.println(new Solution().isPalindrome(head)); 12 } 13 } 14 class Solution { 15 public boolean isPalindrome(ListNode head) { 16 ListNode slow=head,fast=head; 17 while(fast!=null&&fast.next!=null){ 18 slow=slow.next;//慢指针一次移动一个结点 19 fast=fast.next.next;//快指针一次移动两个结点 20 } 21 if(fast!=null)//结点个奇数为时会出现fast！=null，此时将slow右移一个 22 slow=slow.next; 23 slow=reverse(slow); 24 ListNode h=head;//定义h是为了不破坏原来链表 25 while(slow!=null){ 26 if(h.val!=slow.val) 27 return false; 28 h=h.next; 29 slow=slow.next; 30 } 31 return true; 32 } 33 //reverse为反转链表，详见LeetCode206 34 public ListNode reverse(ListNode head){ 35 ListNode pre=null; 36 ListNode current=head; 37 ListNode next=null; 38 while(current!=null){ 39 next=current.next; 40 current.next=pre; 41 pre=current; 42 current=next; 43 } 44 return pre; 45 } 46 } 47 class ListNode { 48 int val; 49 ListNode next; 50 ListNode(int x) { val = x; } 51 }
程序结果：
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
