234. 回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 1.入栈法

思路：
1.将链表压入栈中
2.比较头节点和stack.peek()值是否相同，相同则为回文链表，否则出栈最后一个节点
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;
    }

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(n),由于需要开辟一个栈，所以空间复杂度为O(n)

• 2.快慢指针 + 反转

思路：
1.使用快慢指针找出中间节点
2.将后半部分链表反转
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;
        }
        //针对链表长度是奇数或偶数的处理
        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;
    }

复杂度分析：
时间复杂度：O(n)
空间复杂度：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));
    }

• 结果

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

• 源码

• 我会随时更新新的算法，并尽可能尝试不同解法，如果发现问题请指正

• Github