LeetCode 234 回文链表
题目:请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
使用O(n) 时间复杂度和 O(1) 空间复杂度。
- 使用快慢指针找到中间位置(偶数的话这里取前一个)
- 反转链表
- 遍历原始链表和反转链表,比较是否相等。长度不同的话,当较短的比较结束即跳出循环。
- (还原链表,题目中没要求,这里就不做了,思路就是再用一遍反转,然后中间结点拼起来)
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
|
class Solution { public boolean isPalindrome(ListNode head) { if(head == null) return true; ListNode mid = firstEndOfHalf(head); ListNode reverse = revList(mid.next); return cmpList(reverse, head); } public ListNode revList(ListNode head){ ListNode prev = null; ListNode curr = head; ListNode post = null; while(curr != null){ post = curr.next; curr.next = prev; prev = curr; curr = post; } return prev; } public boolean cmpList(ListNode l1, ListNode l2){ while(l1 != null && l2 != null){ if(l1.val != l2.val){ return false; } l1 = l1.next; l2 = l2.next; } return true; } public ListNode firstEndOfHalf(ListNode head){ if(head == null) return null; ListNode slow = head; ListNode fast = head; while(fast.next != null && fast.next.next!= null){ slow = slow.next; fast = fast.next.next; } return slow; } }
|