[Leetcode] Palindrome Linked List 回文鏈表

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

摘要：代碼尋找中點(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ù)雜度

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

思路

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

代碼

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        ListNode fast = head;
        ListNode slow = head;
        // 尋找中點(diǎn)
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        // 記錄第二段鏈表的第一個(gè)節(jié)點(diǎn)
        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;
    }
}