面试题 02.06. 回文链表
难度简单78
编写一个函数,检查输入的链表是否是回文的。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
if(head.next.next == null) return head.val == head.next.val;
ListNode mid = middleNode(head);
ListNode rHead = reverse(mid.next);
ListNode lHead = head;
while(rHead!=null){
if(lHead.val != rHead.val) return false;
rHead = rHead.next;
lHead = lHead.next;
}
return true;
}
public ListNode middleNode(ListNode head){
ListNode fast = head;
ListNode slow = head;
while(fast.next !=null && fast.next.next !=null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
public ListNode reverse(ListNode head){
ListNode newHead = null;
while(head !=null){
ListNode tmp = head.next;
head.next = newHead;
newHead=head;
head=tmp;
}
return newHead;
}
}
网友评论