[Leetcode] Palindrome Linked List 回文鏈表

glumes 發(fā)布于2019-08-14 12:28 / 1160人閱讀

摘要：代碼尋找中點記錄第二段鏈表的第一個節(jié)點將第一段鏈表的尾巴置空將第二段鏈表的尾巴置空依次判斷

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?

反轉鏈表 復雜度

時間 O(N) 空間 O(1)

思路

兩個指針都從頭出發(fā)，快指針每次兩步，慢指針每次一步，這樣快指針的下一個或下下個為空時，慢指針就在鏈表正中間那個節(jié)點了（如果鏈表有偶數(shù)個節(jié)點則在靠近頭那側的）。然后我們從慢指針的下一個開始，把后面的鏈表都反轉（Reverse Linked List），然后我們再從頭和從尾同時向中間前進，就可以判斷該鏈表是不是回文了。

代碼

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        ListNode fast = head;
        ListNode slow = head;
        // 尋找中點
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        // 記錄第二段鏈表的第一個節(jié)點
        ListNode secondHead = slow.next;
        ListNode p1 = secondHead;
        ListNode p2 = p1.next;
        // 將第一段鏈表的尾巴置空
        slow.next = null;
        while(p1 != null && p2 != null){
            ListNode tmp = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = tmp;
        }
        // 將第二段鏈表的尾巴置空
        secondHead.next = null;
        // 依次判斷
        while(p1 != null){
            if(head.val != p1.val) return false;
            head = head.next;
            p1 = p1.next;
        }
        return true;
    }
}

GPU云服務器云服務器 linked palindrome LeetCode LeetCode_String

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64501.html

LeetCode 234：回文鏈表 Palindrome Linked List

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

luqiuwen 2019-08-16 18:41 評論0 收藏0
LeetCode 234：回文鏈表 Palindrome Linked List

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

hlcc 2019-07-31 11:30 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

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

tain335 2019-08-26 10:28 評論0 收藏0
前端 | 每天一個 LeetCode

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

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

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

warmcheng 2019-08-26 10:09 評論0 收藏0