[数据结构与算法] 算法基础（九）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 算法基础（九）– 回文链表 -> 正文阅读

[数据结构与算法]算法基础（九）– 回文链表

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1] 输出：true

示例 2：

输入：head = [1,2] 输出：false

提示：

链表中节点数目在范围[1, 105] 内 0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list

解法描述

遍历链表，依次将每个元素放入栈中，然后重新从头结点遍历，与栈中弹出元素比对是否相等，完全相等则为回文结构；
在方法1基础上进行优化，栈中不必保存所有元素，只需定位到链表中点，然后将后续元素放入栈中，再从头结点（与栈中弹出元素）开始比对；
不使用栈结构来实现：首先还是定位到链表的中点或上中间（偶数个节点情况下定位中间两个节点的上一个）结点，然后将中间结点后面的链表元素改变指针方向，中点或上中间结点的元素next指向null，最后，头结点指针与尾结点指针同时向中间遍历，比较各个元素是否相等。
最最后，不要忘记改变会原链表的指向。。

编码实现

方法1：

public boolean isPalindrome(ListNode head) {
    Stack<ListNode> stack = new Stack<>();
    ListNode cur = head;
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }

    ListNode pop;
    while (!stack.isEmpty()) {
        pop = stack.pop();
        if (pop.val != head.val) {
            return false;
        }
        head = head.next;
    }
    return true;
}

方法2

public boolean isPalindrome(ListNode head) {
    // 0 或 1个元素时，直接返回true
    if (head == null || head.next == null) {
        return true;
    }

    // 定位 下中点 或 中点下一个
    ListNode midOrDown = head.next;
    ListNode fast = head;
    // 2  s=2, f=1
    // 3  s=3, f=3
    // 4  s=3, f=3
    // 5  s=4, f=5
    while (fast.next != null && fast.next.next != null) {
        midOrDown = midOrDown.next;
        fast = fast.next.next;
    }
    
    Stack<ListNode> stack = new Stack<>();
    ListNode cur = midOrDown;
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }

    while (!stack.isEmpty()) {
        ListNode pop = stack.pop();
        if (pop.val != head.val) {
            return false;
        }
        head = head.next;
    }

    return true;
}

方法3

public boolean isPalindrome(ListNode head) {
    // 0 或 1个元素时，直接返回true
    if (head == null || head.next == null) {
        return true;
    }

    // 定位 上中点 或 中点
    ListNode midOrUp = head;
    ListNode fast = head;
    // 2  s=1, f=1
    // 3  s=2, f=3
    // 4  s=2, f=3
    // 5  s=3, f=5
    while (fast.next != null && fast.next.next != null) {
        midOrUp = midOrUp.next;
        fast = fast.next.next;
    }

    ListNode cur = midOrUp.next;
    midOrUp.next = null;

    // 链表后半部分反转
    ListNode pre = midOrUp;
    ListNode next;
    while (cur != null) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }

    ListNode last = pre;
    // 开始比对
    cur = pre;
    ListNode left = head;
    boolean res = true;
    while (left != null && cur != null) {
        if (left.val != cur.val) {
            res = false;
            break;
        }
        left = left.next;
        cur = cur.next;
    }

    // 恢复链表
    pre = null;
    cur = last;
    while (cur != null) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }

    return res;
}