11月9日面试题

题目

面试时要求O(n)时间复杂度和O(1)空间复杂度。

解析

O(1)空间复杂度不借助额外的空间进行操作，只在原链表中进行操作。回文要求判断第一个和最后一个节点，第二个和倒数第二个节点，直到中间的节点。因为单向链表，尾节点开始无法向前遍历，需要从中间的节点开始，把后半段的链表翻转，然后两个半段的链表进行比较即可。

1. 找到中间节点，如果节点个数为单数，找到中间的那个节点；如果节点个数为偶数，找到中间两个节点后面的那个节点。
2. 这个中间节点作为后半段链表的头节点，对后半段链表进行翻转。
3. 逐个比较两段链表的每一个元素，判断是否相等。

下面代码翻转后半部链表之后，各节点关系如图所示：

代码

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;
}