11月9日面試題

題目

面試時要求O(n)時間復雜度和O(1)空間復雜度。

解析

O(1)空間復雜度不借助額外的空間進行操作，只在原鏈表中進行操作。回文要求判斷第一個和最后一個節(jié)點，第二個和倒數(shù)第二個節(jié)點，直到中間的節(jié)點。因為單向鏈表，尾節(jié)點開始無法向前遍歷，需要從中間的節(jié)點開始，把后半段的鏈表翻轉(zhuǎn)，然后兩個半段的鏈表進行比較即可。

1. 找到中間節(jié)點，如果節(jié)點個數(shù)為單數(shù)，找到中間的那個節(jié)點；如果節(jié)點個數(shù)為偶數(shù)，找到中間兩個節(jié)點后面的那個節(jié)點。
2. 這個中間節(jié)點作為后半段鏈表的頭節(jié)點，對后半段鏈表進行翻轉(zhuǎn)。
3. 逐個比較兩段鏈表的每一個元素，判斷是否相等。

下面代碼翻轉(zhuǎn)后半部鏈表之后，各節(jié)點關系如圖所示：

代碼

public boolean isPalindrome(ListNode head) {
    //如果鏈表為null，或者只有一個節(jié)點直接返回true
    if (null == head || head.next == null){
        return true;
    }
    //翻轉(zhuǎn)后半部分鏈表
    ListNode head2 = reverseList(head);
    //比較兩半部分的鏈表節(jié)點
    while (head != null && head2 != null){
        //如果兩個節(jié)點不滿足回文，直接返回false
        if (head.val != head2.val){
            return false;
        }
        head = head.next;
        head2 = head2.next;
    }
    return true;
}

//找到中間節(jié)點
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;
}

//以中間節(jié)點為頭節(jié)點，翻轉(zhuǎn)后半部鏈表
private ListNode reverseList(ListNode head){
    ListNode newHead = midNode(head);

    ListNode first = newHead;
    ListNode second = newHead.next;
    //中間節(jié)點為新的的頭節(jié)點，next引用要置空
    //否則后半部的新鏈表最后兩個節(jié)點會產(chǎn)生循環(huán)指向關系
    first.next = null;
    ListNode third;
    while (second != null){
        third = second.next;
        second.next = first;
        first = second;
        second = third;
    }
    return first;
}