成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

LeetCode 234：回文鏈表 Palindrome Linked List

luqiuwen / 679人閱讀

摘要：請判斷一個(gè)鏈表是否為回文鏈表。然后是判斷是否是回文鏈表不考慮進(jìn)階要求的話，方法千千萬。好在這道題只要求返回布爾值，即便把原鏈表改變了也不用擔(dān)心。然后從原鏈表頭節(jié)點(diǎn)與反轉(zhuǎn)后后半部分鏈表頭節(jié)點(diǎn)開始對比值即可。

?
請判斷一個(gè)鏈表是否為回文鏈表。

Given a singly linked list, determine if it is a palindrome.

示例 1:

輸入: 1->2
輸出: false

示例 2:

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

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

Follow up:
Could you do it in O(n) time and O(1) space?

解題思路：

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

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

不考慮進(jìn)階要求的話，方法千千萬?？梢园亚鞍氩糠謺捍嫒胄碌臄?shù)組、鏈表、哈希表等等數(shù)據(jù)結(jié)構(gòu)，然后依次倒序取出，與后半部分鏈表每個(gè)節(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)鏈表，時(shí)間復(fù)雜度為 O(n),空間復(fù)雜度為 O(1)，所以符合要求。然后從原鏈表頭節(jié)點(diǎn) 與 反轉(zhuǎn)后后半部分鏈表頭節(jié)點(diǎn)開始對比值即可。

反轉(zhuǎn)鏈表的各種詳細(xì)方法在前幾日的那道題中已經(jīng)詳細(xì)解答過，未看過的朋友可以先看那一篇：LeetCode 206：反轉(zhuǎn)鏈表 Reverse Linked List

Java： 
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)的下一個(gè)節(jié)點(diǎn)
            head.next = pre;//當(dāng)前節(jié)點(diǎn)下一個(gè)指向pre
            pre = head;//刷新pre
            head = tmp;//刷新當(dāng)前節(jié)點(diǎn)為tmp
        }
        return pre;
    }
}
Python： 
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        fast, slow = head, head
        if not fast or not fast.next: return True
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        newHead = self.reverseList(slow.next)
        while newHead:
            if newHead.val != head.val: return False
            newHead = newHead.next
            head = head.next
        return True

    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        pre, tmp = None, None
        while (head):
            tmp = head.next
            head.next = pre
            pre = head
            head = tmp
        return pre

歡迎關(guān)注公.眾號一起學(xué)習(xí): 愛寫B(tài)ug

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/75577.html

相關(guān)文章

  • LeetCode 234：回文鏈表 Palindrome Linked List

    摘要：請判斷一個(gè)鏈表是否為回文鏈表。然后是判斷是否是回文鏈表不考慮進(jìn)階要求的話，方法千千萬。好在這道題只要求返回布爾值，即便把原鏈表改變了也不用擔(dān)心。然后從原鏈表頭節(jié)點(diǎn)與反轉(zhuǎn)后后半部分鏈表頭節(jié)點(diǎn)開始對比值即可。 ?請判斷一個(gè)鏈表是否為回文鏈表。 Given a singly linked list, determine if it is a palindrome. 示例 1: 輸入: 1->...

    hlcc 評論0 收藏0

  • [Leetcode] Palindrome Linked List 回文鏈表

    摘要：代碼尋找中點(diǎn)記錄第二段鏈表的第一個(gè)節(jié)點(diǎn)將第一段鏈表的尾巴置空將第二段鏈表的尾巴置空依次判斷 Palindrome Linked List Given a singly linked list, determine if it is a palindrome. Follow up: Could you do it in O(n) time and O(1) space? 反轉(zhuǎn)鏈表 復(fù)...

    glumes 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

    摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...

    tain335 評論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

    張漢慶 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

    摘要：微信公眾號記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...

    warmcheng 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<