234. Palindrome Linked List

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up: Could you do it in O(n) time and O(1) space?

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */public class Solution public boolean isPalindrome(ListNode head) { ListNode slow=head; ListNode fast=head; if(fast==null||fast.next==null)//0个节点或是1个节点 return true; while(fast.next!=null&&fast.next.next!=null) { fast=fast.next.next; slow=slow.next; } //对链表后半段进行反转 ListNode midNode=slow; ListNode firNode=slow.next;//后半段链表的第一个节点 ListNode cur=firNode.next;//插入节点从第一个节点后面一个开始 firNode.next=null;//第一个节点最后会变最后一个节点 while(cur!=null) { ListNode nextNode=cur.next;//保存下次遍历的节点 cur.next=midNode.next; midNode.next=cur; cur=nextNode; } //反转之后对前后半段进行比较 slow=head; fast=midNode.next; while(fast!=null) { if(fast.val!=slow.val) return false; slow=slow.next; fast=fast.next; } return true; } }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。