力扣学习笔记——234. 回文链表

解题思路

反转后半部分链表

链表反转的实现思路有很多，参考：https://mp.weixin.qq.com/s?__biz=MzU0ODMyNDk0Mw==&mid=2247488340&idx=1&sn=c3d6adc9f737672aab544931502dda2e&chksm=fb418074cc360962b46cb764068a5818f58bed6a4cd05ef61057823918d95f3a192550f02408&scene=21#wechat_redirect

实现代码

反转后半部分链表

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        // 遍历到链表中点后一位
        while (fast != null && fast.next != null) { // 利用快慢指针的特性，当快指针遍历完后，慢指针刚好是链表中点后一位
            fast = fast.next.next;
            slow = slow.next;
        }
        if (fast != null) slow = slow.next; // fast != null 说明链表长度是奇数，此时slow在中点，需要往后移动一位
        // 反转slow
        slow = reverse(slow);

        // 将快指针重置到head
        fast = head;

        // 对比fast和slow
        while(slow != null) {
            if (fast.val != slow.val) return false;
            fast = fast.next;
            slow = slow.next;
        }
        return true;
        
    }

    public ListNode reverse(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        if (stack.isEmpty()) return null;
        ListNode node = stack.pop();
        ListNode dummy = node; // 作为反转后的头部
        while (!stack.isEmpty()) {
            ListNode temp = null;
            temp = stack.pop();
            node.next = temp;
            node = node.next;
        }
        node.next = null; // 最后需要将 node.next 至空 不然会造成环
        return dummy;
    }
}

反转链表可以进一步优化：

让链表进行原地反转

public ListNode reverse(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            // 保存下一个节点
            ListNode temp = head.next;
            // 让每次访问的链表头部作为新链表的头部
            head.next = newHead;
            // 更新新链表
            newHead = head;
            // 重新赋值，继续访问
            head = temp;
        }
        return newHead;
    }