234. 回文鏈表

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

示例 1:

輸入: 1->2
輸出: false

示例 2:

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/palindrome-linked-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處膘怕。

• 1.入棧法

思路：
1.將鏈表壓入棧中
2.比較頭節(jié)點和stack.peek()值是否相同番捂，相同則為回文鏈表摸袁，否則出棧最后一個節(jié)點
3.比較鏈表長度的一半即可

image.png

public static class ListNode {

        private int val;
        private ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        //用于測試用例
        public ListNode(int[] arr) {
            if (arr == null || arr.length == 0) throw new NullPointerException("array is Empty");
            this.val = arr[0];
            ListNode cur = this;
            for (int i = 1; i < arr.length; i++) {
                cur.next = new ListNode(arr[i]);
                cur = cur.next;
            }
        }

        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            ListNode cur = this;
            while (cur != null) {
                res.append(cur.val + "->");
                cur = cur.next;
            }
            res.append("NULL");
            return res.toString();
        }

    }

    public static boolean isPalindrome(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        int size = 0;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
            size++;
        }
        int mid = size / 2;
        for (int i = 0; i < mid; i++) {
            if (head.val == stack.peek().val) {
                head = head.next;
                stack.pop();
            } else {
                return false;
            }
        }
        return true;
    }

復(fù)雜度分析：
時間復(fù)雜度：O(n)
空間復(fù)雜度：O(n),由于需要開辟一個棧惕虑，所以空間復(fù)雜度為O(n)

• 2.快慢指針 + 反轉(zhuǎn)

思路：
1.使用快慢指針找出中間節(jié)點
2.將后半部分鏈表反轉(zhuǎn)
3.與前半部分進行比較，如果相同則是回文鏈表

image.png

public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //針對鏈表長度是奇數(shù)或偶數(shù)的處理
        ListNode last = fast == null ? slow : slow.next;
        ListNode cur = last;
        ListNode prev = null;
        while (cur != null) {
            ListNode p = cur.next;
            cur.next = prev;
            prev = cur;
            cur = p;
        }
        while (prev != null) {
            if (head.val == prev.val) {
                head = head.next;
                prev = prev.next;
            } else {
                return false;
            }
        }
        return true;
    }

復(fù)雜度分析：
時間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

• 測試用例

public static void main(String[] args) {
         int[] arr = new int[] {1, 2, 1, 2, 1};
         ListNode listNode = new ListNode(arr);
         System.out.println(listNode);
         System.out.println("是否是回文鏈表" + isPalindrome2(listNode));
    }

• 結(jié)果

1->2->1->2->1->NULL
是否是回文鏈表true

• 源碼

• 我會隨時更新新的算法睛挚，并盡可能嘗試不同解法邪蛔，如果發(fā)現(xiàn)問題請指正

• Github