解答
思路：将链表分成两段，然后将后面一段进行翻转，在逐项进行比较。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | class Solution { public boolean isPalindrome(ListNode head) { if(head == null || head.next == null){ return true; } ListNode temp = head; ListNode temp2 = head; //只有两个数字时，后面一段的链表是第二个 ListNode temp1 = head.next; int len = 0; //遍历出链表有效数字 while(temp!=null){ temp = temp.next; len++; } for(int i=0; i<len/2-1;i++){ temp2 = temp2.next; temp1 = temp1.next; } //分成两部分 temp2.next = null; //有效数字是奇数个，后一段的链表在往后移一位 if(len%2!=0){ temp1 = temp1.next; } return isEqual(head,reverse(temp1)); } //翻转链表 private ListNode reverse(ListNode head) { ListNode newHead = null; while (head != null) { ListNode nextNode = head.next; head.next = newHead; newHead = head; head = nextNode; } return newHead; } //逐个判断是否相等 private boolean isEqual(ListNode l1, ListNode l2) { while (l1 != null && l2 != null) { if (l1.val != l2.val) return false; l1 = l1.next; l2 = l2.next; } return true; }} |
帖子还没人回复快来抢沙发