色五月婷婷导航,不卡无码免费,欧美日韩性爱视频,蜜乳久久,天天日天天射大香蕉,中国黄色视频网站,最新在线无码热a,丁香花激情网

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做 回文鏈表，我們先來看題面：

https://leetcode-cn.com/problems/palindrome-linked-list/

Given the head of a singly linked list, return true if it is a palindrome.

請判斷一個鏈表是否為回文鏈表。

示例

示例 1:

輸入: 1->2
輸出: false

示例 2:

輸入: 1->2->2->1
輸出: true

進(jìn)階：
你能否用 O(n) 時間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題？

解題

https://www.imooc.com/article/289808

首先是尋找鏈表中間節(jié)點(diǎn)，這個可以用快慢指針來解決，快指針?biāo)俣葹?，慢指針?biāo)俣葹?，快指針遍歷完鏈表時，慢指針剛好走到中間節(jié)點(diǎn)（相對）。

然后是判斷是否是回文鏈表：

不考慮進(jìn)階要求的話，方法千千萬?？梢园亚鞍氩糠謺捍嫒胄碌臄?shù)組、鏈表、哈希表等等數(shù)據(jù)結(jié)構(gòu)，然后依次倒序取出，與后半部分鏈表每個節(jié)點(diǎn)的值對比即可。更簡單的是直接用數(shù)據(jù)結(jié)構(gòu) - 棧，先進(jìn)后出，把節(jié)點(diǎn)壓入棧中，到中間節(jié)點(diǎn)后，依次從棧中彈出節(jié)點(diǎn)，與后半部分的節(jié)點(diǎn)值對比即可。

直接思考進(jìn)階要求，在 O(1) 的空間復(fù)雜度下，只能選擇操作原鏈表來完成該題。好在這道題只要求返回布爾值，即便把原鏈表改變了也不用擔(dān)心。我們可以將鏈表后半部分反轉(zhuǎn)，利用迭代法反轉(zhuǎn)鏈表，時間復(fù)雜度為 O(n),空間復(fù)雜度為 O(1)，所以符合要求。然后從原鏈表頭節(jié)點(diǎn) 與反轉(zhuǎn)后后半部分鏈表頭節(jié)點(diǎn)開始對比值即可。

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        if (fast == null || fast.next == null) return true;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode newHead = reverseList(slow.next);
        while (newHead != null) {
            if (head.val != newHead.val) return false;
            head = head.next;
            newHead = newHead.next;
        }
        return true;
    }
  //反轉(zhuǎn)鏈表函數(shù)--詳情請看前文
    private ListNode reverseList(ListNode head) {
        if (head.next == null) return head;
        ListNode pre = null;
        ListNode tmp;
        while (head!= null) {
            tmp = head.next;//tmp暫存當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)
            head.next = pre;//當(dāng)前節(jié)點(diǎn)下一個指向pre
            pre = head;//刷新pre
            head = tmp;//刷新當(dāng)前節(jié)點(diǎn)為tmp
        }
        return pre;
    }
}