11月9日面试题
题目
面试时要求O(n)时间复杂度和O(1)空间复杂度。
解析
O(1)空间复杂度不借助额外的空间进行操作，只在原链表中进行操作。回文要求判断第一个和最后一个节点，第二个和倒数第二个节点，直到中间的节点。因为单向链表，尾节点开始无法向前遍历，需要从中间的节点开始，把后半段的链表翻转，然后两个半段的链表进行比较即可。
- 找到中间节点，如果节点个数为单数，找到中间的那个节点；如果节点个数为偶数，找到中间两个节点后面的那个节点。
- 这个中间节点作为后半段链表的头节点，对后半段链表进行翻转。
- 逐个比较两段链表的每一个元素，判断是否相等。
下面代码翻转后半部链表之后，各节点关系如图所示：
代码
public boolean isPalindrome(ListNode head) {
//如果链表为null，或者只有一个节点直接返回true
if (null == head || head.next == null){
return true;
}
//翻转后半部分链表
ListNode head2 = reverseList(head);
//比较两半部分的链表节点
while (head != null && head2 != null){
//如果两个节点不满足回文，直接返回false
if (head.val != head2.val){
return false;
}
head = head.next;
head2 = head2.next;
}
return true;
}
//找到中间节点
private ListNode midNode(ListNode head){
int size = 0;
ListNode n = head;
while (n != null){
size++;
n = n.next;
}
int mid = size / 2;
n = head;
while (mid > 0){
n = n.next;
mid--;
}
return n;
}
//以中间节点为头节点，翻转后半部链表
private ListNode reverseList(ListNode head){
ListNode newHead = midNode(head);
ListNode first = newHead;
ListNode second = newHead.next;
//中间节点为新的的头节点，next引用要置空
//否则后半部的新链表最后两个节点会产生循环指向关系
first.next = null;
ListNode third;
while (second != null){
third = second.next;
second.next = first;
first = second;
second = third;
}
return first;
}
